【LeetCode】406. 根据身高重建队列

最新推荐文章于 2025-03-09 18:56:46 发布

jiiiiiaaaa

最新推荐文章于 2025-03-09 18:56:46 发布

阅读量461

点赞数

分类专栏： leetcode 文章标签：算法数据结构 leetcode

本文链接：https://blog.csdn.net/jiiiiiaaaa/article/details/109715580

版权

leetcode 专栏收录该内容

57 篇文章

订阅专栏

这篇博客介绍了LeetCode 406题目的解法，通过两种不同的策略——从低到高和从高到低考虑，详细阐述了如何根据身高和前面高个子人数重建队列。解题思路包括利用排序和队列插入来解决身高相同的情况，分析了时间复杂度和空间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例：

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

方法一：从低到高考虑

思路与算法

当每个人的身高都不相同时，如果我们将他们按照身高从小到大进行排序，那么就可以很方便地还原出原始的队列了。

为了叙述方便，我们设人数为 n，在进行排序后，它们的身高依次为 $h_0, h_1, \cdots, h_{n-1}$ ，且排在第 i 个人前面身高大于 $h_i$ 的人数为 $k_i$ 。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 i 个人时：

第 $0, \cdots, i-1$ 个人已经在队列中被安排了位置，并且他们无论站在哪里，对第 i 个人都没有任何影响，因为他们都比第 i 个人矮；
而第 $i+1, \cdots, n-1$ 个人还没有被放入队列中，但他们只要站在第 i 个人的前面，就会对第 i 个人产生影响，因为他们都比第 i 个人高。

如果我们在初始时建立一个包含 n 个位置的空队列，而我们每次将一个人放入队列中时，会将一个「空」位置变成「满」位置，那么当我们放入第 i 个人时，我们需要给他安排一个「空」位置，并且这个「空」位置前面恰好还有 $k_i$ 个「空」位置，用来安排给后面身高更高的人。也就是说，第 i 个人的位置，就是队列中从左往右数第 $k_i+1$ 个「空」位置。

那么如果有身高相同的人，上述 $k_i$ 定义中的大于就与题目描述中要求的大于等于不等价了，此时应该怎么修改上面的方法呢？我们可以这样想，如果第 i 个人和第 j 个人的身高相同，即 $h_i = h_j$ ，那么我们可以把在队列中处于较后位置的那个人的身高减小一点点。换句话说，对于某一个身高值 h，我们将队列中第一个身高为 h 的人保持不变，第二个身高为 h 的人的身高减少 $\delta$ ，第三个身高为 hh 的人的身高减少 $2\delta$ ，以此类推，其中 $\delta$ 是一个很小的常数，它使得任何身高为 h 的人不会与其它（身高不为 h 的）人造成影响。

如何找到第一个、第二个、第三个身高为 h 的人呢？我们可以借助 k 值，可以发现：当 $h_i = h_j$ 时，如果 $k_i > k_j$ ，那么说明 i 一定相对于 j 在队列中处于较后的位置（因为在第 j 个人之前比他高的所有人，一定都比第 i 个人要高），按照修改之后的结果， $h_i$ 略小于 $h_j$ ，第 ii 个人在排序后应该先于第 jj 个人被放入队列。因此，我们不必真的去对身高进行修改，而只需要按照 $h_i$ 为第一关键字升序， $k_i$ 为第二关键字降序进行排序即可。此时，具有相同身高的人会按照它们在队列中的位置逆序进行排列，也就间接实现了上面将身高减少 $\delta$ 这一操作的效果。

这样一来，我们只需要使用一开始提到的方法，将第 i 个人放入队列中的第 $k_i+1$ 个空位置，即可得到原始的队列。

C++

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
        });
        int n = people.size();
        vector<vector<int>> ans(n);
        for (const vector<int>& person: people) {
            int spaces = person[1] + 1;
            for (int i = 0; i < n; ++i) {
                if (ans[i].empty()) {
                    --spaces;
                    if (!spaces) {
                        ans[i] = person;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

Python

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (x[0], -x[1]))
        n = len(people)
        ans = [[] for _ in range(n)]
        for person in people:
            spaces = person[1] + 1
            for i in range(n):
                if not ans[i]:
                    spaces -= 1
                    if spaces == 0:
                        ans[i] = person
                        break
        return ans

复杂度分析

时间复杂度： $O(n^2)$ ，其中 n 是数组 people 的长度。我们需要 O(nlogn) 的时间进行排序，随后需要 $O(n^2)$ 的时间遍历每一个人并将他们放入队列中。由于前者在渐近意义下小于后者，因此总时间复杂度为 $O(n^2)$ 。
空间复杂度：O(logn)，即为排序需要使用的栈空间。

方法二：从高到低考虑

思路与算法

同样地，我们也可以将每个人按照身高从大到小进行排序，处理身高相同的人使用的方法类似，即：按照 $h_i$ 为第一关键字降序， $k_i$ 为第二关键字升序进行排序。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 i 个人时：

第 $0, \cdots, i-1$ 个人已经在队列中被安排了位置，他们只要站在第 i 个人的前面，就会对第 i 个人产生影响，因为他们都比第 i 个人高；
而第 $i+1, \cdots, n-1$ 个人还没有被放入队列中，并且他们无论站在哪里，对第 i 个人都没有任何影响，因为他们都比第 i 个人矮。

在这种情况下，我们无从得知应该给后面的人安排多少个「空」位置，因此就不能沿用方法一。但我们可以发现，后面的人既然不会对第 i 个人造成影响，我们可以采用「插空」的方法，依次给每一个人在当前的队列中选择一个插入的位置。也就是说，当我们放入第 i 个人时，只需要将其插入队列中，使得他的前面恰好有 $k_i$ 个人即可。

C++

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]);
        });
        vector<vector<int>> ans;
        for (const vector<int>& person: people) {
            ans.insert(ans.begin() + person[1], person);
        }
        return ans;
    }
};

Python

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        n = len(people)
        ans = list()
        for person in people:
            ans[person[1]:person[1]] = [person]
        return ans

复杂度分析