406. 根据身高重建队列
题目描述
有一群人原本站成一队，现在顺序被打乱了。输入数组 people，people[i] = [h, k] 表示某个人身高为 h，并且在原队列中他前面恰好有 k 个身高不低于 h 的人。
请还原出原来的队列，以数组 queue 的形式返回。queue[j] = [h, k] 表示排在第 j 位的人，queue[0] 在队首。
题目保证一定能还原出这样的队列。
示例 1
输入：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]]
解释：例如 [5,2] 前面有 [5,0]、[7,0] 两人不矮于 5；[4,4] 前面有 4 人不矮于 4。
示例 2
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
解释：[1,4] 前面的 4,5,2,3 都比 1 高；[6,0] 前面没有人不矮于 6。
数据范围
1 <= people.length <= 20000 <= h <= 10^60 <= k < people.length- 保证队列可以还原。
解题思路：从高到低排序插入
先安排高个子。按身高从高到低排序，身高相同时 k 小的在前。依次处理每个人时，已经站好的人都不比他矮，所以他的 k 恰好等于“他前面要有几个已站好的人”，直接插到下标 k 处即可。之后再插入的人都更矮（或同高但 k 更大、插在更后面），不会改变他前面“不比他矮”的人数。
为什么正确
处理完前 t 个人后，res 中每个人前面“身高 >= 自己”的人数都正好等于自己的 k。
复杂度分析
时间 O(n²)（排序 O(n log n)，每次插入最坏 O(n)），空间 O(n)。
易错点
身高相同时必须 k 小的先插，否则后插入的同高者会把先插的人往后挤，破坏其 k；如果从矮到高处理，矮个子插入时还不知道后面高个子会站在哪里。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda p: (-p[0], p[1]))
res = []
for p in people:
res.insert(p[1], p)
return resclass Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
List<int[]> res = new ArrayList<>();
for (int[] p : people) {
res.add(p[1], p);
}
return res.toArray(new int[0][]);
}
}class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];
});
vector<vector<int>> res;
for (auto& p : people) {
res.insert(res.begin() + p[1], p);
}
return res;
}
};func reconstructQueue(people [][]int) [][]int {
sort.Slice(people, func(i, j int) bool {
if people[i][0] != people[j][0] {
return people[i][0] > people[j][0]
}
return people[i][1] < people[j][1]
})
res := [][]int{}
for _, p := range people {
k := p[1]
res = append(res, nil)
copy(res[k+1:], res[k:])
res[k] = p
}
return res
}var reconstructQueue = function(people) {
people.sort((a, b) => a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1]);
const res = [];
for (const p of people) {
res.splice(p[1], 0, p);
}
return res;
};function reconstructQueue(people: number[][]): number[][] {
people.sort((a, b) => a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1]);
const res: number[][] = [];
for (const p of people) {
res.splice(p[1], 0, p);
}
return res;
}其他解法
两种方法都先排序再逐个放置：从高到低时后放的人不影响已放的人，可以直接插入；从低到高时先放的人不影响后放的人，需要预留空位。
解法 2：从低到高放空位 时间 O(n²)，空间 O(n)
按身高升序排序，身高相同时按 k 降序。准备 n 个空位，依次放置每个人。比他矮的人已经放好且不会影响他，后放的人都不比他矮，所以他前面要留出 k 个空位给这些人。于是把他放进从左数第 k + 1 个空位。
不需要在数组中间插入元素，只需找空位。用树状数组或线段树找第 k + 1 个空位，可以优化到 O(n log n)；主解法的插入操作不易这样优化。
class Solution:
def reconstructQueue(self, people):
people.sort(key=lambda p: (p[0], -p[1]))
n = len(people)
res = [None] * n
for p in people:
spaces = p[1] + 1
for i in range(n):
if res[i] is None:
spaces -= 1
if spaces == 0:
res[i] = p
break
return resclass Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
int n = people.length;
int[][] res = new int[n][];
for (int[] p : people) {
int spaces = p[1] + 1;
for (int i = 0; i < n; i++) {
if (res[i] == null) {
spaces--;
if (spaces == 0) {
res[i] = p;
break;
}
}
}
}
return res;
}
}class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
});
int n = people.size();
vector<vector<int>> res(n);
for (auto& p : people) {
int spaces = p[1] + 1;
for (int i = 0; i < n; i++) {
if (res[i].empty()) {
spaces--;
if (spaces == 0) {
res[i] = p;
break;
}
}
}
}
return res;
}
};func reconstructQueue(people [][]int) [][]int {
sort.Slice(people, func(i, j int) bool {
if people[i][0] != people[j][0] {
return people[i][0] < people[j][0]
}
return people[i][1] > people[j][1]
})
n := len(people)
res := make([][]int, n)
for _, p := range people {
spaces := p[1] + 1
for i := 0; i < n; i++ {
if res[i] == nil {
spaces--
if spaces == 0 {
res[i] = p
break
}
}
}
}
return res
}var reconstructQueue = function(people) {
people.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
const n = people.length;
const res = new Array(n).fill(null);
for (const p of people) {
let spaces = p[1] + 1;
for (let i = 0; i < n; i++) {
if (res[i] === null) {
spaces--;
if (spaces === 0) {
res[i] = p;
break;
}
}
}
}
return res;
};function reconstructQueue(people: number[][]): number[][] {
people.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
const n = people.length;
const res: (number[] | null)[] = new Array(n).fill(null);
for (const p of people) {
let spaces = p[1] + 1;
for (let i = 0; i < n; i++) {
if (res[i] === null) {
spaces--;
if (spaces === 0) {
res[i] = p;
break;
}
}
}
}
return res as number[][];
}