题目链接

406. 根据身高重建队列 - 力扣（LeetCode）

题目描述

people[i]=[hi,ki]表示打乱顺序的队列中，

第i个人的身高为hi，原先队列中排在i前面的身高大于等于``i的有ki个人，

输出还原后的队列

输入输出样例

1
2
3
4
5
6
7
8
9
10
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

题目解释

仔细读题发现可以先放置身高比较高的人(这种人影响比较大)

代码

个人实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // 按照h降序，k升序排序
        sort(people.begin(), people.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
             });
        // 依次插入队列中，此时队列中的每个人都比未插入的人高或者前面
        // 这样只要把第i个人插入到ki个位置即可
        vector<vector<int>> res;
        for (auto p : people) {
            res.insert(res.begin() + p[1], p);
        }
        return res;
    }
};

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/queue-reconstruction-by-height/solutions/486066/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // 按h升序，按k降序
        // 比较绕，意思是，从小到大插入people，然后要保证前面有k个空位
        // 这k个空位是为了插入比people更高的人
        sort(people.begin(), people.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
             });

        vector<vector<int>> ans(people.size());
        // 按照顺序插入
        for (auto p : people) {
            // 考虑0位置
            int blank = -1;
            for (int i = 0; i < people.size(); i++) {
                if (ans[i].empty()) {
                    blank++;
                    if (blank == p[1]) {
                        ans[i] = p;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};