LeetCode 406. 根据身高重建队列——多维排序贪心的正确性分析
LeetCode 406. 根据身高重建队列——多维排序贪心的正确性分析
适读人群：Java中高级工程师、算法面试备战者 | 阅读时长：约22分钟 | 难度：中等
开篇故事
这道题第一次见到我是懵的。两个维度的约束——身高和前面的高个子数——怎么同时满足？直觉告诉我应该先处理某一维，但先处理哪维、怎么处理，完全没有头绪。
那时候我尝试了先按 k 排序，发现身高约束满足不了；又尝试先按 h 排序，发现 k 约束需要插入操作，才豁然开朗——这道题的本质是个"插入"问题，不是"交换"问题。
领悟了这一点，代码就很自然了：先按身高从大到小排（身高相同则 k 小的在前），然后按照每个人的 k 值，把他们依次插入到结果数组的第 k 个位置。
但为什么这样做是正确的？每次插入会影响前面已插入人的位置，怎么保证最终每个人的约束都满足？这正是本篇的核心：多维排序贪心的正确性分析。
一、题目解析
题目： 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi，前面正好有 ki 个身高大于或等于 hi 的人。重新构造并返回输入数组 people 所表示的队列。
示例：
- 输入：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]]
关键约束： 每个人的约束是"前面有 ki 个身高 >= hi 的人"，注意是"大于等于"，包括相同身高。
直觉分析：
如果按 k 排序（k 小的先处理），则 k=0 的人排在最前面，这没问题。但当我们处理 k=1 的人时，需要在已排好的人中插入某个位置，而"前面高个子数"取决于已经放置的所有高个子，后续还会插入更多人，这就使得判断变得复杂。
如果按 h 从大到小排序（高个子先处理），情况就不同了：每当我们插入一个身高为 h 的人时，之后插入的所有人身高都 <= h，他们对"h 的前面高个子数"没有任何贡献（因为后面的人身高不高于 h，不满足"高个子"的条件）。因此，当我们把某人插入到位置 k 时，"前面高个子数恰好为 k"这个约束在后续插入不会被破坏。
二、解法一：暴力模拟（O(n³)，理解题意）
思路
穷举所有排列，检查每个排列是否满足所有人的约束。
import java.util.*;
public class Solution_Brute {
public int[][] reconstructQueue(int[][] people) {
int n = people.length;
int[] perm = new int[n];
for (int i = 0; i < n; i++) perm[i] = i;
// 使用全排列检验
return tryAll(people, perm, 0);
}
private int[][] tryAll(int[][] people, int[] perm, int pos) {
if (pos == perm.length) {
// 验证这个排列是否合法
if (isValid(people, perm)) {
int[][] result = new int[perm.length][2];
for (int i = 0; i < perm.length; i++) {
result[i] = people[perm[i]];
}
return result;
}
return null;
}
for (int i = pos; i < perm.length; i++) {
int tmp = perm[i]; perm[i] = perm[pos]; perm[pos] = tmp;
int[][] res = tryAll(people, perm, pos + 1);
if (res != null) return res;
tmp = perm[i]; perm[i] = perm[pos]; perm[pos] = tmp;
}
return null;
}
private boolean isValid(int[][] people, int[] perm) {
int n = perm.length;
for (int i = 0; i < n; i++) {
int h = people[perm[i]][0], k = people[perm[i]][1];
int cnt = 0;
for (int j = 0; j < i; j++) {
if (people[perm[j]][0] >= h) cnt++;
}
if (cnt != k) return false;
}
return true;
}
}复杂度： O(n! × n²)，完全不可用。
三、解法二：先按 h 降序排再按 k 插入（LinkedList 实现）
思路
核心步骤：
- 按 h 降序排序，h 相同时按 k 升序排序。
- 遍历排序后的数组，将每个人插入到结果列表的第 k 个位置。
为什么这是正确的——贪心正确性分析：
性质 A（插入不影响高个子的计数）： 当我们处理身高为 h 的人 p 时，结果列表中已有若干身高 >= h 的人（因为我们按 h 降序处理）。后续还未处理的人身高都 <= h。
如果我们将 p 插入到位置 k，则 p 前面恰好有 k 个已插入的人（这些人身高都 >= h，因为他们是按降序先于 p 处理的）。
后续插入的人身高 <= h，他们可能被插入到 p 前面，但他们不算"高个子"（身高 < h），不影响 p 的约束计数。
若后续插入的人身高 = h，他们的 k 值一定 > p 的 k 值（因为相同身高按 k 升序排，p 的 k 更小，先被处理），所以他们被插入的位置会在 p 之后，也不影响 p 的计数。
结论： 将 p 插入位置 k 后，p 的约束 [h, k] 永久满足，不会被后续插入破坏。
代码
import java.util.*;
public class Solution {
public int[][] reconstructQueue(int[][] people) {
// 步骤1：排序——h降序，h相同时k升序
Arrays.sort(people, (a, b) -> {
if (a[0] != b[0]) return b[0] - a[0]; // h不同：h大的在前
return a[1] - b[1]; // h相同：k小的在前
});
// 步骤2：按k值依次插入到结果列表
// 使用LinkedList支持O(1)的中间插入（但实际Java LinkedList插入是O(n)的，因为需要遍历到位置k）
LinkedList<int[]> result = new LinkedList<>();
for (int[] person : people) {
result.add(person[1], person); // 在第k个位置插入
}
return result.toArray(new int[people.length][]);
}
}复杂度分析
- 时间复杂度： O(n²)——排序 O(n log n)，插入 O(n) 次，每次 LinkedList 插入 O(n)（需要遍历到位置）。
- 空间复杂度： O(n)，LinkedList 存储结果。
四、解法三：排序+数组插入（优化版，含 Mermaid 图）
思路
用 ArrayList 代替 LinkedList，逻辑更清晰。虽然 ArrayList 的中间插入也是 O(n)，但实际常数更小，且代码更易读。
代码
import java.util.*;
public class Solution_ArrayList {
public int[][] reconstructQueue(int[][] people) {
// 排序：身高降序，身高相同时k升序
Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
List<int[]> list = new ArrayList<>();
for (int[] p : people) {
// 将当前人插入到下标为k的位置
// ArrayList.add(index, element) 会将index及之后的元素右移
list.add(p[1], p);
}
return list.toArray(new int[list.size()][]);
}
}步骤验证（对应 Mermaid 图）
初始排序后：[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
- 插入 [7,0] 到位置 0：结果 = [[7,0]]
- 插入 [7,1] 到位置 1：结果 = [[7,0],[7,1]]（[7,1] 前面有1个身高>=7的人 ✓）
- 插入 [6,1] 到位置 1：结果 = [[7,0],[6,1],[7,1]]（[6,1] 前面有1个身高>=6的人 ✓）
- 插入 [5,0] 到位置 0：结果 = [[5,0],[7,0],[6,1],[7,1]]（[5,0] 前面有0个身高>=5的人 ✓）
- 插入 [5,2] 到位置 2：结果 = [[5,0],[7,0],[5,2],[6,1],[7,1]]（[5,2] 前面有2个身高>=5的人 ✓）
- 插入 [4,4] 到位置 4：结果 = [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]（[4,4] 前面有4个身高>=4的人 ✓）
复杂度分析
- 时间复杂度： O(n²)，ArrayList 中间插入 O(n)，共 n 次。
- 空间复杂度： O(n)。
五、举一反三
多维排序贪心的通用思路
当问题中有两个约束维度时，一般先"固定"更强的那个维度（将其排序后按序处理），让较弱的约束通过插入/调整满足。
LeetCode 1710. 卡车上的最大单元数 每个箱子有数量和每箱单元数，要在卡车限重内装最多单元数。按单元数降序排，贪心装最多单元的箱子——这是一维贪心。
LeetCode 2007. 从双倍数组中还原原数组 将一个数组中每个元素翻倍混入原数组，还原原数组。按绝对值排序，贪心地配对最小的未配对元素和它的2倍。
身高重建队列——逆向思维
有时候"从大到小"插入比"从小到大"更直观：
- 先处理高个子：他们的约束完全由"目前已有的人"决定，后续矮个子不影响。
- 矮个子插入时，已有的高个子视作"占位符"，矮个子在"高个子视角"中是透明的。
六、踩坑实录
坑一：排序比较器——h相同时的排序方向搞反
// 错误：h相同时k也降序排
Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);
// 正确：h相同时k升序排
Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);如果 h 相同时 k 也降序排，例如 [5,2] 在 [5,0] 前面处理，[5,2] 被插入位置 2，然后 [5,0] 被插入位置 0，但此时 [5,0] 前面没有身高 >= 5 的人（只有之后插入的高个子才算），而 [5,2] 已经在位置 2，会导致计数错误。
坑二：LinkedList.add(index, element) 和 ArrayList.add(index, element) 的性能差异
虽然 LinkedList 理论上在中间插入是 O(1)，但实际上 Java 的 LinkedList.add(index, element) 首先需要 O(n) 时间找到第 index 个节点，然后才是 O(1) 插入。所以两者实际时间复杂度都是 O(n²)，不要被"链表插入是O(1)"误导。
坑三：忘记处理 people.length == 0 的边界
代码中 list.toArray(new int[list.size()][]) 在 list 为空时返回空数组 int[0][]，是合法的。但如果有其他写法可能会有边界问题，注意始终测试空输入。
坑四：认为按 k 升序排序然后逐步调整也可行
一些同学尝试按 k 升序排序，然后用某种方式"移动"不符合条件的人。但这样做的问题是：移动高个子会影响矮个子的 k 值计数，形成连锁反应，逻辑非常复杂。高个子先处理的优势在于：高个子不受矮个子影响，一旦放好位置就永久固定。
七、总结
身高重建队列是多维排序贪心的典型题，核心洞察是：先处理对后续影响最小的维度。
高个子先处理的理由是：高个子的 k 值约束只与其他高个子有关，矮个子的插入不会影响高个子的计数；反之，矮个子的 k 值约束同时受高矮两者影响，所以矮个子要在高个子确定位置后再处理。
这个思路在面试中非常有价值——当你遇到多维约束的构造题，首先问自己：哪个维度的约束更"强"（影响面更广），哪个更"弱"（影响面更窄）？先排定强约束，再用弱约束指导插入位置。
| 解法 | 时间复杂度 | 空间复杂度 | 推荐 |
|---|---|---|---|
| 暴力全排列 | O(n! × n²) | O(n) | 仅理解 |
| LinkedList插入 | O(n²) | O(n) | 清晰 |
| ArrayList插入 | O(n²) | O(n) | 推荐 |
补充深入讲解：多维排序贪心的设计原则与拓展
为什么高个子先处理是关键
理解身高重建队列的核心，在于理解"处理顺序"和"约束影响关系"之间的联系。
每个人的约束是"前面有 ki 个身高 >= hi 的人"。这个约束涉及两个维度：身高（hi）和位置（通过前面的人数间接决定）。当我们处理一个人时，希望他的约束在确定之后就不会再被后续操作破坏。
如果先处理矮个子会发生什么？矮个子的约束是"前面有 ki 个身高 >= hi 的人"，高个子也满足"身高 >= hi"的条件。所以当我们插入一个高个子时，所有矮个子的"前面高个子数"可能会增加，破坏之前确定的约束。
而先处理高个子则不同。当我们已经排好了一些高个子之后，再插入一个矮个子（身高 h_low）时，矮个子对已有高个子的约束（前面有多少个高个子）没有影响，因为矮个子不算"高个子"（身高不满足 >= 高个子身高的条件）。
这个"单向影响"关系是整个算法的核心：高个子不受矮个子影响，矮个子受高个子影响。因此，先确定高个子的位置（不受后续影响），再根据高个子的位置和自己的 k 值来决定矮个子的位置。
约束图分析
从约束图的角度来看，这道题的约束可以建模为有向图：如果身高 ha >= hb，则 a 对 b 有影响（a 的位置会影响 b 的约束计数）。
对于高度不同的两个人 a（较高）和 b（较低），a 对 b 有影响但 b 对 a 无影响，关系是单向的。因此，我们应该先确定"被影响少"的节点（高个子），再确定"被影响多"的节点（矮个子）。这是一种"拓扑排序"思想的应用。
对于高度相同的两个人，他们互相影响（都算对方的"高个子"）。在这种情况下，按 k 升序处理：k 小的先处理，k 大的后处理，这样 k 小的被插入较前的位置，后续 k 大的插入时，前面已经有了足够多的"高个子"来满足其约束。
插入操作的性能考量
本题的时间复杂度是 O(n²)，主要来自 ArrayList 的中间插入操作（每次插入需要移动后续元素）。在 n 较大时，可以考虑以下优化方案：
方案一：使用平衡二叉树（或者跳表）维护结果，支持 O(log n) 的第 k 个元素查找和 O(log n) 的插入。总时间复杂度 O(n log n)。Java 没有直接支持"按秩查找"的标准库，需要用树状数组（Binary Indexed Tree，BIT/Fenwick Tree）来实现 O(log n) 的"找第 k 个空位"操作。
方案二：树状数组优化。将 n 个位置想象为一个有 n 个空槽的序列，初始所有槽为空。按高度降序处理，每次"找第 ki 个空槽"（表示前面有 ki 个已插入的人），然后将这个槽标记为占用。树状数组可以在 O(log n) 时间内回答"第 k 个空槽在哪里"的查询。
不过对于 n <= 2000 的题目约束，O(n²) 完全可以通过，无需复杂的数据结构优化。
多维排序贪心的通用原则总结
通过这道题，我们可以总结出一个通用的多维约束排序贪心设计原则：
第一步，分析约束的影响关系。哪个维度的约束影响面更广（影响更多其他人的约束）？哪个维度的约束影响面更窄（只受少数人影响）？
第二步，按影响面从大到小的顺序处理。先处理"影响面大"的维度，即先确定那些一旦放好位置就不受后续影响的元素。这样可以保证每次放好位置后，约束就永久满足。
第三步，对于影响面相同的元素，按约束值（如本题的 k 值）排序，确保相同影响面的元素之间的相对顺序也正确。
这个三步法可以推广到很多类似的多维排序贪心题目，如任务调度（任务有截止时间和执行时长两个维度）、背包变体等。
与实际工程问题的对应
这类多维排序贪心在工程中的典型应用场景：
任务优先级调度：在有截止时间约束的任务调度系统中，需要确定任务的执行顺序。如果任务 A 的截止时间比任务 B 早，则 A 的调度时间对 B 没有影响（A 先执行不会延误 B），但 B 的延迟执行可能影响 A 的截止时间。类似本题，应该先处理截止时间早的任务。
分层架构的依赖管理：在微服务架构中，底层服务（被依赖多）应该优先部署和稳定，上层服务（依赖多）后部署。这正是"按依赖层级从底层到顶层处理"的思想，本质上与本题相同。
身高重建队列的一句话总结
身高重建队列的核心洞察可以用两句话概括：高个子先确定位置，矮个子不影响高个子的计数；矮个子后插入，按照 k 值找位置时，已有的高个子就是它的"计数基准"，后续的矮个子是透明的。这两句话说清了为什么高个子先处理、为什么用 k 值直接插入是正确的。
把这两句话和一个具体的例子（比如 [7,0],[7,1],[6,1],[5,0],[5,2],[4,4] 的插入过程）结合起来，就能在面试中清晰地讲清楚这道题的算法思路，展示对贪心正确性的深刻理解，而不只是背了一个代码模板。
多维排序贪心的通用思路在算法面试中非常有价值。遇到多个维度约束的构造题，首先分析维度间的影响关系，然后按影响力从强到弱排序，依次确定。这个思路的本质是"拓扑排序"思想在贪心构造中的应用：先确定不依赖他人的独立变量，再根据已确定的变量来确定依赖变量。