我来给你讲解 LeetCode 第 406 题「根据身高重建队列」。

题目描述

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hᵢ, kᵢ] 表示第 i 个人的身高为 hᵢ，前面正好有 kᵢ 个身高大于或等于 hᵢ 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue，其中 queue[j] = [hⱼ, kⱼ] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例：

输入：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]]

解题思路分析

第一步：理解问题核心

这个问题要求我们根据每个人的身高和前面更高人数来重建队列。关键观察点：

• 身高更高的人不受身高更矮的人影响（矮的人站在高的人前面或后面都不影响高的人的 k 值）
• 但矮的人站在高的人前面会影响矮人的 k 值计算

第二步：寻找排序策略

核心思路：先处理身高最高的人，因为他们的位置最容易被确定。

为什么？

• 身高最高的人前面不可能有比他们更高的人，所以他们的 k 值就是他们应该在的位置索引
• 当我们插入一个较矮的人时，已经排好队的都是比ta高或相等的人，所以只需要数前面有多少人就能确定插入位置

第三步：具体排序规则

1. 按身高降序排序（从高到矮）
2. 身高相同时，按 k 值升序排序（k 小的排在前面）

对于示例：

排序前：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
排序后：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

第四步：插入重建队列

从排序后的人员列表中逐个插入到结果队列：

• 每个人的 k 值就是ta应该插入的位置索引
• 因为我们已经按身高降序排列，所以插入时前面的人都是身高 ≥ 当前人身高的人

插入过程：

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]]

第五步：算法实现

def reconstructQueue(people):
    # 按身高降序，k值升序排序
    people.sort(key=lambda x: (-x[0], x[1]))
    
    result = []
    # 按 k 值作为索引插入
    for p in people:
        result.insert(p[1], p)
    
    return result

第六步：复杂度分析

• 时间复杂度：O(n²) - 排序需要 O(n log n)，但插入操作最坏情况下需要 O(n²)
• 空间复杂度：O(n) - 存储结果队列

第七步：为什么这个算法正确？

关键理解：当我们按身高降序插入时，每个新插入的人：

1. 比队列中已存在的所有人都矮（或相等）
2. 插入位置由 k 值决定，k 值表示前面要有多少个更高的人
3. 由于已排序，插入时前面的人确实都是 ≥ 当前身高的

这种方法保证了重建后的队列满足每个人的 k 值要求。