406. 根据身高重建队列
题目描述
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。
示例
示例 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]]
示例 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]]
解题思路
第一步：理解问题本质
每个人 [h, k] 要求前面恰好有 k 个身高 >= h 的人。关键问题是：按什么顺序插入能保证正确性？
第二步：贪心策略
核心洞察：
- 先处理身高高的人，再处理身高矮的人
- 身高相同的人，按
k从小到大排列 - 每个人插入到结果列表的第
k个位置
为什么正确：
- 当处理身高为
h的人时，前面已经插入的都是身高>= h的人 - 所以当前人前面的人数恰好等于其在队列中的位置
- 身高矮的人后插入，不会影响身高高的人的相对位置（因为矮的人不算在
k的计数中）
完整代码实现
from typing import List
class Solution:
"""
根据身高重建队列 - 贪心算法
按身高降序，身高相同按 k 升序
依次插入到结果列表的第 k 个位置
时间复杂度：O(n log n)
空间复杂度：O(n)
"""
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 按身高降序，身高相同则按前面人数升序
people.sort(key=lambda x: (-x[0], x[1]))
ans = list()
for person in people:
# 将当前人插入到 ans[person[1]] 位置
ans[person[1]:person[1]] = [person]
return ans
示例推演
以 people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 为例：
排序后：[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
插入过程：
| 步骤 | 当前人 | 插入位置 | 结果列表 |
|---|---|---|---|
| 1 | [7,0] | 0 | [[7,0]] |
| 2 | [7,1] | 1 | [[7,0],[7,1]] |
| 3 | [6,1] | 1 | [[7,0],[6,1],[7,1]] |
| 4 | [5,0] | 0 | [[5,0],[7,0],[6,1],[7,1]] |
| 5 | [5,2] | 2 | [[5,0],[7,0],[5,2],[6,1],[7,1]] |
| 6 | [4,4] | 4 | [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] |
最终答案：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力 | O(n!) | O(n) | 枚举所有排列 |
| 贪心（最优） | O(n log n) | O(n) | 排序 + 插入 |
易错点总结
1. 排序规则
错误：按身高升序。
正确：按身高降序，这样先处理高的人，后插入的矮的人不会影响高的人的 k 值。
2. 身高相同时
身高相同的人要按 k 升序排列，这样 k 小的人先插入，不会占用 k 大的人的位置。