企业官网建设流程全解析

1. 题目是啥：一段绕来绕去的描述，先把它翻译成人话

1.1 原题描述和示例

第 406 题的意思是：给你一个二维数组people，数组里的每个人用一个长度为 2 的小数组[h, k]表示，h是这个人的身高，k表示在重建后的队列里，这个人前面必须恰好有k个身高大于等于h的人。

注意关键点：这里说的“前面”不是原始输入数组里的顺序，而是你最终构造出的队列顺序。输入给的这个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]]

我们随便验证两个人：[5,2]这个人的前面是[5,0]和[7,0]，这两个人身高都大于等于 5，正好有 2 个，满足 k=2；再验证[4,4]，它前面有[5,0]、[7,0]、[5,2]、[6,1]四个人，都大于等于 4，也正好满足 k=4。

1.2 这个数组到底代表什么

很多新手第一次看到这题会懵，因为每个[h,k]看起来像一个坐标，身高是 x，k 是 y，但实际上它是一组“排队约束”。你可以把这想象成一群身高不同的人需要站成一行，每个人都能报出两个数据：我多高，以及我前面至少得有多少个不比我矮的人。

注意，是“不比我矮的人”，也就是身高大于等于我的人。矮个子站在高个子前面没关系，高个子不会去数矮个子，所以矮个子对高个子的 k 值没有任何影响。但反过来，高个子站在矮个子前面，会被矮个子数进自己的 k 值里。

这个不对称性是整道题的核心。只要抓住“高个子不数矮个子”这一点，解法就顺了。

1.3 容易误解的几个点

第一个误解是：以为k就是当前这个人最终站的下标。其实不是，k表示的是“前面身高不低于我的人数”，不是“前面总人数”，也不直接等于最终下标。最终下标和前面有多少人、这些人多高都有关系。

第二个误解是：以为原始数组里那个顺序有意义。题目给的输入顺序是随机的，你不需要在原始顺序上做局部调整，而是要把所有人重新排列，所以思路可以完全跳出来，把一个个人当成一张张待插入的卡片。

第三个误解是：忽略身高相等的情况。k 的定义是“身高大于等于我”，所以身高相同的人也会互相被数进去。这一点在排序的时候会导致一个很隐蔽的坑，后面会重点讲。

2. 贪心解法是怎么一步步想出来的

2.1 先排高的还是先排矮的

一看到需要满足多个约束，很多人第一反应是从矮个子开始排，因为矮个子比较好插队，但实际操作起来很麻烦。真正舒服的顺序是先处理高个子。

道理很简单：一个高个子前面到底站了谁，只取决于前面那些身高不低于他的人；那些比他矮的人，他根本不在乎。所以如果先把最高的那批人排好，之后再插入任何矮个子，都不会破坏高个子已经满足的 k 值。这个性质就是贪心选择成立的基础。

而如果你先排矮个子，后面插入高个子的时候，矮个子前面的人数可能会变多，k 值直接被破坏，非常难处理。

2.2 高个子优先的直觉

想象一下你手里有一堆人，先只看最高的那些人。因为没有人比他们更高，所以他们互相之间怎么站，决定了彼此的 k 值。处理完最高的人之后，再来处理第二高的人，这时第二高的人前面必须有多少“不矮于他的人”，这些“不矮于他的人”已经在队列里了，他只需要插到合适的位置，让前面正好有 k 个这样的人就行。

用一个生活化的例子：高个子是"大哥"，矮个子是"小弟"。大哥排队时只会在意前面有没有其他大哥，小弟站在大哥前面，大哥根本不会多看一眼。所以你先把大哥排好，再让小弟一个个插进去，大哥的世界完全不受影响。

这就是贪心算法里常见的套路：先处理影响力大、约束强的人，再处理影响力小的人。局部最优选择是“每次挑当前最高的那个人，把他放到他自己指定的位置”，最终全局也一定是对的。

2.3 同身高时的排序细节

身高相同的两个人会互相数进 k 值里，所以处理顺序不能随便。

正确做法是：身高从高到低排，身高相同的人按 k 值从小到大排。

举个例子，假设有两个人[7,0]和[7,1]。如果先把[7,1]插进空队列，它要在下标 1 的位置插入，但队列现在是空的，直接越界报错。就算不越界，等[7,0]再插入到它前面，[7,1]前面的人数就多了一个，计数也会乱。

按 k 从小到大处理，[7,0]先插入到下标 0，然后[7,1]插入到下标 1，结果就是[[7,0],[7,1]]，两个人都满足。所以“身高降序、k 升序”这两条排序规则缺一不可。

2.4 为什么插入位置就是 k

这是整道题最关键的一步。我们把所有人按“身高降序、k 升序”排好，然后依次处理。此时，队列里已经存在的人，身高都大于等于当前这个人。当前这个人的 k 表示“他前面需要有 k 个身高大于等于他的人”，那么直接把他插入到列表下标为 k 的位置，他前面正好有 k 个人，而且这 k 个人全都满足“身高大于等于他”的条件。

为什么插入后不会破坏已有人？因为当前这个人的身高只会比已经处理过的人矮，或者等于他们。如果比他矮，他插到某人前面也不会被那个人数进去；如果身高相同，因为我们保证相同身高按 k 升序处理，后插入的同身高人会站在合适的位置，不会让先插入的同身高人 k 值变多。

每次插入只考虑当前这个人，不考虑其他，但结果自然是正确的，这就是贪心的魅力。

3. Java 完整实现与关键代码拆解

3.1 比较器怎么写更稳

先写排序。很多人图省事直接这么写：

Arrays.sort(people, (a, b) -> b[0] - a[0]);

如果只有身高降序，相同身高的人顺序不确定，后面很容易出问题。更好的写法是同时比较 k：

Arrays.sort(people, (a, b) -> { if (a[0] != b[0]) { return Integer.compare(b[0], a[0]); } return Integer.compare(a[1], b[1]); });

这里用Integer.compare而不是直接做减法，是为了防止两个极端整数相减时溢出。虽然这个题的数据范围下不太可能溢出，但养成用Integer.compare的习惯更安全，面试时也能少一个被追问的点。

3.2 add(index, element) 与列表选择

排序完，关键操作就是调用List.add(index, element)，把当前数组插入到下标为 k 的位置。Java 里ArrayList和LinkedList都实现了这个接口，都能用。

不少老题解会无脑选LinkedList，理由是“中间插入多，链表插入快”。但说实话，LinkedList.add(index, element)并不是 O(1)，它需要先从头或者尾开始遍历，找到下标为 index 的节点，然后再插入，最坏也是 O(n)。而ArrayList.add(index, element)虽然需要移动后续元素，但底层是连续内存，随机访问很快，在这个数据规模下反而表现不差。

这个题 n 最多也就 2000 左右，所以ArrayList完全够用，代码也更简洁。我用ArrayList居多，只有当你需要频繁在头部插入且数据量很大的时候，才值得认真考虑LinkedList。

3.3 完整代码

import java.util.*; public class Solution { public int[][] reconstructQueue(int[][] people) { // 第 1 步：排序 // 身高从高到低，身高相同则 k 从小到大 Arrays.sort(people, (a, b) -> { if (a[0] != b[0]) { return Integer.compare(b[0], a[0]); } return Integer.compare(a[1], b[1]); }); // 第 2 步：逐个插入到下标 k 的位置 List<int[]> queue = new ArrayList<>(); for (int[] p : people) { queue.add(p[1], p); } // 第 3 步：转成二维数组返回 return queue.toArray(new int[queue.size()][]); } }

3.4 代码逐行说明

第 1 步排序完成后，people数组本身就被重新排列了。这样做不影响正确性，因为我们后面只是按顺序读取每个人，并不需要保留原始输入顺序。

第 2 步里queue.add(p[1], p)是核心。p[1]是 k，p[0]是身高。add(index, element)会把p这个数组对象插入到队列地下标为 k 的位置，原本这个位置及后面的元素自动往右移一格。

第 3 步转成二维数组。注意toArray(T[] a)这个方法，传入new int[queue.size()][][]，它会把列表内容填进这个新数组。如果直接调用不带参数的toArray()，返回的是Object[]，不能强转成int[][]，很多人在这里报过类型转换错误。

4. 边界条件、复杂度和常见错误排雷

4.1 小心比较器溢出

虽然这个题身高范围很小，写b[0] - a[0]不会真溢出，但只要你养成习惯用Integer.compare，换到别的排序题就不容易踩坑。尤其当你排序的 key 是一个很大的整数时，return a - b可能因为符号溢出导致比较器返回结果和预期相反，严重时还会违反比较器的传递性，让排序结果随机化。

4.2 空列表插入不是从 0 开始会越界

ArrayList.add(index, element)要求 index 必须满足0 <= index <= size。空列表的 size 是 0，此时如果直接插入到下标 1，就会抛IndexOutOfBoundsException。

这也是为什么排序规则必须是“身高降序、k 升序”。如果同身高的人先处理 k 大的，空列表插不下；就算能插下，后续同身高的人插入也会把计数搞乱。排序错了，插入大概率直接崩。

4.3 时间复杂度与空间复杂度

排序的时间复杂度是 O(n log n)。后面每一步插入，ArrayList.add(index, element)最坏要移动 O(n) 个元素，一共 n 次插入，所以整体是 O(n^2)。

空间复杂度方面，queue这个列表里存的是people数组中元素的引用，并没有复制人，所以额外空间主要是列表本身的开销，可以认为是 O(n)。

O(n^2) 在这题能过吗？能。n 上限只有 2000 左右，n 的平方是 400 万级别的操作，对 Java 来说非常快，不用担心性能。

排序：O(n log n) 插入：O(n^2) 总体：O(n^2) 空间：O(n)

4.4 常见错误对照表

下面这些错误我平时在评论区看得最多，自己早期也犯过，整理成一个速查表：

5. 手动模拟与测试用例记录

5.1 官方示例手推

拿开头那个例子手动推一遍。排序后的顺序是：

[7,0] [7,1] [6,1] [5,0] [5,2] [4,4]

逐步插入：

最后结果和题目答案完全一致。注意[7,1]被一路挤到了队列末尾，这是正常的，因为后面插入的矮个子不被他数进 k 值，所以不影响他的正确性。

5.2 自己构造的几组验证用例

写这种算法题，光靠官方样例不够，我会自己构造几组极端用例来验证。

第一组：单个人

输入：[[9,0]] 输出：[[9,0]]

这组不出错是最基本的。

第二组：不同身高，k 都是 0

输入：[[9,0],[7,0]] 输出：[[7,0],[9,0]]

这里 k 都是 0，说明每个人前面不能有任何身高不低于自己的人，所以矮的必须在前。顺序是身高升序：7 在前，9 在后。

第三组：全部同身高

输入：[[6,2],[6,0],[6,1]] 排序后：[[6,0],[6,1],[6,2]] 输出：[[6,0],[6,1],[6,2]]

同身高时 k 升序，最终结果就是按 k 排序的结果，因为每个人前面正好有下标那么多个同身高的人。如果排序时不把 k 升序处理，这种全同身高用例必挂。

5.3 调试时打印什么

我在本地调试时会加一个校验函数，构造完队列之后立刻验证一遍：

public static boolean isValid(int[][] queue) { for (int i = 0; i < queue.length; i++) { int count = 0; for (int j = 0; j < i; j++) { if (queue[j][0] >= queue[i][0]) { count++; } } if (count != queue[i][1]) { return false; } } return true; }

这个方法实现的就是题目的定义：对每个人，扫描他前面所有人，统计身高大于等于他的人，然后和 k 比较。每构造完一个用例都跑一遍校验，能快速定位到底是排序出了问题，还是插入位置出了问题。

5.4 和别的思路对比

除了“排序加插入”这个贪心解法，也有人会想到用树状数组做，把每个人按身高从小到大排序，然后在空位上二分查找第 k+1 个空位，复杂度能降到 O(n log n)。但说实话，对这个题的数据范围来说，O(n^2) 已经足够，而且“排序加插入”代码量最小，最好解释。

还有一种思路是每次都从剩余人里找满足条件的人，复杂度更高，而且实现麻烦，不建议。

我自己的建议是，面试或者刷题时先掌握这个贪心解法，它已经能覆盖绝大多数考察场景。树状数组的版本适合作为扩展阅读，不是这道题的重点。

6. 实战测试与调试心得

6.1 写题时的思考顺序

我拿到题不会直接写代码，先问自己三个问题：

• 谁先安排比较合理？答案是高个子先安排。
• 同身高的人怎么区分先后？答案是 k 小的人先安排。
• 插入位置应该用什么值？答案是直接用 k 作为列表下标。

这三个问题想清楚后，代码基本就是三行核心逻辑：排序、循环、插入。剩下的全是 LinkedList、ArrayList 这种细枝末节。

6.2 遇到排序结果不对怎么排查

如果你发现输出队列的 k 值不对，先不要怀疑插入逻辑，大概率是排序规则错了。可以把排序后的数组打出来看一遍，再手动模拟一遍插入过程。我排错时的习惯是，在循环里打印每一步的队列状态，这样很快能定位到是哪一步插入破坏了条件。

6.3 我对这类贪心题的经验总结

这类“约束重建”题目，核心就是找“谁不影响谁”。在本题里，矮个子不影响高个子，所以先排高个子是天然的正确顺序。很多贪心题都是这个套路：先处理对别人影响更小、但被别人影响更大的人或物。

这个题还有一个很值得记住的细节：同名或等值元素怎么排序。数据处理里经常会遇到“主排序字段相同，必须用次级字段决定先后”的情况，第 406 题就是非常典型的案例，学会了之后，很多排序题都能举一反三。