根据身高重建队列如何用贪心求解？（LeetCode 406）

简化版

每个人用 [h, k] 表示：h 是身高，k 是排在他前面、身高 ≥ 他的人数。打乱后要重建这个队列。贪心策略：先按身高 h 降序排、身高相同则按 k 升序排；然后依次把每个人「插入到结果列表的第 k 个位置」。因为按身高从高到矮处理，插入矮个子时不会影响已排好的高个子的 k 值，所以插到下标 k 处，前面恰好就有 k 个不比他矮的人。

详细版

int[][] reconstructQueue(int[][] people) {
    // 身高降序；身高相同则 k 升序
    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);      // 插入到下标 k 的位置
    }
    return res.toArray(new int[people.length][]);
}

排序规则：身高 h 降序（高的先站），身高相同 k 升序（k 小的先插，站前面）。
按 k 插入：因为已插入的都比当前人高或等高，把当前人插到下标 k，前面正好 k 个「身高 ≥ 他」的人，满足 k 的定义。
复杂度：排序 O(n log n)，插入 O(n²)（ArrayList 中间插入要移动元素）。

完整版教学

一、难点：两个维度互相牵制

每个人有两个属性 h 和 k，且 k 的含义依赖于队列里其他人（前面有几个不矮于他的）。如果同时考虑两个维度，很难落笔。贪心的思路是固定一个维度、消解另一个维度的干扰——先按身高排序，让「身高」这个维度变得有序、可控，再专心处理 k。

二、为什么按身高「降序」

k 只关心「前面比我高或和我一样高的人数」，比我矮的人对我的 k 毫无影响。基于这个性质：

如果从高到矮依次安排每个人，那么在安排某个人时，已经站进队列的所有人都不比他矮（都 ≥ 他的身高）。此时他的 k（前面有 k 个不矮于他的）就直接等于「他在当前队列里的下标位置」——把他插到下标 k，前面恰好 k 个人，且这 k 个人全都 ≥ 他，完美满足定义。

反过来若从矮到高排，后面来的高个子会插到矮个子前面，改变矮个子前面「更高的人数」，k 会被打乱——所以必须降序。

三、身高相同为什么按 k 升序

身高相同的人之间，彼此都算「身高 ≥」对方，会互相计入 k。若身高相同，k 小的人排在前面（前面高个子少），k 大的排后面。所以同身高时按 k 升序，先插 k 小的，保证他们之间的相对顺序正确。

举例：[5,0] 和 [5,2] 同身高。k=0 的应在前、k=2 的在后。升序排序让 [5,0] 先插（插到下标 0），[5,2] 后插（插到下标 2），符合各自的 k。若反了，[5,2] 先插到下标 2、[5,0] 再插到下标 0 把它挤到下标 3，[5,2] 的实际 k 就错了。

四、按 k 插入的正确性

排好序后逐个插入 res.add(k, p)：

处理到 p 时，res 里已有的人都不比 p 矮（降序保证）。
把 p 插到下标 k，它前面就有 k 个人，且这 k 个都 ≥ p → 恰好满足 p 的 k 定义。
之后再插入的都是更矮的人，他们插在哪都不影响 p 前面「更高人数」（矮的不计入 p 的 k），所以 p 的 k 一旦满足就永久成立。

这就是贪心选择性质：每一步的插入都不会破坏之前已满足的约束，一步步拼出全局正确的队列。

五、复杂度与优化

用 ArrayList 在中间插入是 O(n) 每次，总 O(n²)。对面试数据量足够。
想更快可用树状数组/线段树维护「空位」，把插入降到 O(n log n)，但代码复杂，一般不要求。
排序本身 O(n log n)。

排序成本是 O(n log n)，但数组列表在下标 k 插入需要搬移，累计最坏 O(n²)，它才是整体瓶颈。若 n 很大，可反向建模为空位选择，并用树状数组查找第 k 个空位降到 O(n log n)。

六、贪心选择为什么不会堵死未来

本题每一步选择是：按身高降序、同高 k 升序；依次把人插入结果下标 k，使已放置者都不矮于当前人。

正确性不能只靠直觉，核心证明是：插入当前人时队列中的人全部更高或同高且已按 k 处理，位置 k 正好保证前面有 k 个合格者；后插矮人不影响计数。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：[(7,0),(7,1),(6,1),(5,0)] 处理7后为[(7,0),(7,1)]，插(6,1)到1即可满足k=1。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：同高必须 k 升序；数组中间插入使时间 O(n²)；非法输入可能出现 k 大于当前长度。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

八、常见误区与追问

误区：按身高升序插入也一样。 后插高个会改变矮个前方计数。
误区：同高顺序无关。 先放较大 k 时当前列表可能不够长且计数错误。
误区：插入后矮人会破坏高个条件。 高个只统计不矮于自己者，矮人不计入。
追问：为什么位置就是 k？ 当前列表所有人都满足高度门槛。
追问：复杂度为何 O(n²)？ ArrayList 中间插入需要搬移元素。
追问：能否优化？ 可用树状数组找第 k 个空位，采用另一排序策略做到 O(n log n)。

九、加强记忆

根据身高重建队列 = 排序 + 按 k 插入的贪心。关键洞察：k 只受「不比自己矮的人」影响，矮个子无所谓。所以身高降序排（同身高时 k 升序），从高到矮依次把每个人插到结果列表的下标 k 处——此时前面的人都 ≥ 他，正好 k 个满足定义，且之后插入的更矮的人不会破坏他。一句话：高个先站定位，矮个按 k 见缝插针，插了也不影响前面的高个。O(n log n) 排序 + O(n²) 插入。

简化版

详细版