这道题在 LeetCode 上编号 406题目名字也很直白根据身高重建队列。我印象里它算得上“贪心 排序”这个组合里最经典的题目之一很多人在准备面试时都会遇到。题面本身不难读懂但是第一次做的时候十有八九会卡在“到底按什么顺序排序、处理完怎么放”这一点上。等你真正想明白了又会发现它背后其实藏着一套挺通用的排序 插入的思维模式。这篇文章我把这道题从建模到两种主流解法再到证明和容易踩的坑完整梳理一遍适合刚刷到链表、排序相关题目的读者也适合想巩固贪心证明思路的人。1. 题目场景与核心建模1.1 先看懂题意再动手题目输入是一个二维数组people里面的每个元素是[h, k]。h表示这个人的身高k表示在这个人前面、且身高不低于他的人数。注意是“不低于”不是“高于”所以和他身高一样的人也要算进去。举个例子输入[[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]期望输出是[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]在原数组中每个[h, k]的信息是“被打乱”的也就是说这个数组并不是一个合法的队列顺序我们需要重新排列这些二元组让最终排列满足每个位置的约束条件。我见过很多人拿到这道题的第一反应是这不就是个二维排序问题吗直接按照h降序、k升序排一下再看输出好像跟答案不完全一致。是的没有这么简单。如果只排一次序就能得到正确结果那这道题就没有必要作为贪心的典型例题了。关键在于排序只是第一步后面还要“按位置插入”。1.2 为什么这是一道排序题而非构造题很多贪心题目的难点不是算法过程本身而是如何把看似复杂的约束条件转成一个可以直接操作的规则。拿这道题来说如果我们真的去模拟“重建队列”最容易想到的办法就是暴力枚举所有排列再检查每个排列是否满足要求。遇到n 6还勉强能跑一旦n到几十甚至几百排列规模爆炸完全不可行。于是我们需要找到一个逐步构造的规则。这里的关键观察是要是我们先处理身高最高的一批人他们前面的位置是完全不受其他更矮的人影响的。因为其他人都不高于他们无论那些矮个子站到哪儿高个子目前看过去的“前面不低于自己的人数”也不会变只会因为后续插入比他们矮的人而把他们的位置往后推。所以解题思路很自然地分层了先搞出身高最高的那部分人把他们按规则排好再把矮的人一个个插进去。这个过程其实就是一个贪心构造每次只关心当前这个人应该站在哪个位置而且这个位置在已经安排好的人群里是唯一确定的。这个思路的特征很明显局部最优决定全局可行。这也是为什么我会把这道题看作“贪心”而不是单纯的“排序”的原因。2. 贪心策略的整体拆解2.1 核心排序维度选择整体解法一般会分两步走。第一步先排序排序规则常见写法是按 h 降序如果 h 相同按 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]]这里有两个维度为什么要先按h降序我们需要一个原则先处理高个子再处理矮个子。原因在于高个子的k约束只受“不低于自己身高的人”影响后面插入的所有更矮的人都不会破坏已经放置好的高个子的特征。所以我们把高个子都找出来先把这批人的队列位置固定下来。但光降序还不够。同身高的人之间彼此也构成“前面不低于自己”的关系所以如果两个人身高一样比如[7, 0]和[7, 1]那么先放谁的差别很大。如果先放[7, 1]再放[7, 0]插入位置会错乱。我们必须在同组内也按k从小到大来处理这样保证每个人插入时他需要看的“前面有几个同身高的人”已经按从小到大的顺序补齐了。2.2 为什么先排身高降序如果反过来先按身高升序处理会麻烦很多。试想矮个子先排好了之后高个子插到队伍里可能会直接插到矮个子的前面。对矮个子来说前面突然多了一个“比他高的人”他原本记录里“前面不低于自己的人数”就失效了。因为那个k是站在最终队列里统计的矮个子前面高个子越多他的约束就越复杂但他又不知道后续会有多少高个子插到他前面所以他无法预先留出位置。身高降序恰恰解决了这个信息不足的问题当前正在插入的第i个人是已经处理过的所有人当中最矮的或并列最矮后面还没处理的都更矮。无论后面的人怎么插都不会影响已经处理好的队列里那些“身高不低于当前人”的计数。换句话说先处理高个子保证“已建队列的数字不会再变化”这样每次插入新人的时候既能满足新人的约束又不会破坏已插入人员的位置正确性。2.3 同身高的人按 k 升序的含义同身高的人之间要按照k从小到大处理这是另一个经常被忽略的细节。如果h相同两个人对于彼此来说都是“不低于自己”的存在所以在同组内部也存在前后依赖。拿[7, 0]和[7, 1]举例。如果先在队列里插入[7, 0]此时数组是[[7, 0]]。这时再插入[7, 1]他要求在队列里前面有 1 个不低于 7 的人所以插到下标 1 的位置得到[[7, 0], [7, 1]]没问题。但要是我们先插入[7, 1]队列里只有[[7, 1]]这一项。再插入[7, 0]时他要求前面有 0 个不低于 7 的人按位置插入到 0 下标得到[[7, 0], [7, 1]]。这么看好像也没问题。但问题是如果场景有 3 个同身高的人而中间夹杂着不同 k 值处理顺序乱掉时中间状态会出现短路。比如[7, 0]、[7, 1]、[7, 2]三个人你如果先插[7, 2]再插[7, 0]最后插[7, 1]虽然最终结果可能侥幸正确但中间每次插在哪、空位怎么数很容易乱套。按k升序处理能保证每个人的插入位置是从前往后连续铺设的不容易出错也是在证明时最有条理的一种方便状态。简单说这样设计排序规则不是想当然而是为了让插入过程天然自洽。3. 从高到低的插入法实现3.1 插入位置论证排序结束之后我们把数组从头到尾遍历一遍每个人插入到一个临时列表的k下标位置。为什么会是k下标因为在已经安排好的队列里当前要处理的这个人是所有已经安排的人里面最矮的或并列最矮。这就意味着他前面的所有人身高都不低于他。既然如此他前面需要的人数k实际上就是最终队列中他前面的人数。并且他插入的位置是按当前下标插的后续比他更矮的人只会插到他后面的位置因为更矮的人下标可能等于当前长度但不会跑到比当前人更靠前的地方把当前人的编号打乱等等……这里需要稍微严谨一点。我再把插入位置为什么是“当前列表的 k 下标”这一点讲透一点。假设现在临时队列里已经有了一批处理完的人这些人的身高都不矮于当前要插入的人x。此时我们要把x放到一个位置并且要满足在x前面恰好有k个人高度不低于x。因为临时列表里现有的人全都不矮于x所以如果x放在下标pos那么他前面的现有人员数量正好等于pos。于是直接把x插入到下标k的位置即可。等将来插入更矮的人y时y要么出现在x前面要么出现在x后面。如果出现在x后面自然不影响x的 k 值如果出现在x前面比如x的k值为 0那么y跑到x前面此时y的身高比x矮所以在x看来y不构成“前面不低于自己”的人。因此x的k值不会变化。这样递归地推导下去每次插入的操作都能保证“旧人不受影响新人得到满足”。3.2 参考代码我习惯用 Java 来写 LeetCode 题解因为 Java 的List支持在指定下标插入元素写起来很直观。public int[][] reconstructQueue(int[][] people) { // 排序身高降序如果身高相同则按 k 升序 Arrays.sort(people, (a, b) - a[0] ! b[0] ? b[0] - a[0] : a[1] - b[1]); Listint[] res new ArrayList(); for (int[] p : people) { res.add(p[1], p); } return res.toArray(new int[res.size()][]); }这版代码非常短。很多人看答案时会奇怪就这么几行代码能算困难题吗其实这道题在 LeetCode 上标的是中等难度代码量确实不大但真正的价值在于你能不能说清楚排序规则为什么是这样、插入下标为什么是k、以及为什么每次都插到k下标就能保证全局正确。这几点总结起来就是一道货真价实的“看似简单但内含深意”的题。如果使用 Python写起来也很简洁class Solution: def reconstructQueue(self, people: List[List[int]]) - List[List[int]]: people.sort(keylambda x: (-x[0], x[1])) res [] for p in people: res.insert(p[1], p) return reskeylambda x: (-x[0], x[1])这一句其实就等价于“身高降序身高相同时 k 升序”。Python 的list.insert也是 O(n) 复杂度整体和 Java 版本是一样的。3.3 正确性证明与复杂度很多人写贪心从不想证明但面试的时候尤其遇到“为什么这样一定对”的追问如果没有提前准备很容易被问住。这里给一个相对严谨的证明框架。证明分三个部分首先排序后当我们依次处理每个人时在i时刻当前列表 L 里只包含身高不低于当前人x的那些人。这个性质由降序排序保证。其次当把x插入到下标k时因为 L 里所有人都不矮于x所以x前面的人数就是k且这些人身高都不低于x满足约束。最后要证明后续处理不会破坏这一点。后续插入的每个人y身高都低于或等于x。如果y身高低于x那么不管y插到x前面还是后面在x看来y都“不够高”不参与计数。如果y身高等于x由于之前同身高的人按k升序处理y的k必不小于x它的插入位置会落在 x 后面或同位置但不会让已经生成的 x 前面的高个子数量改变。综合来看每位已插入的人员约束均保持不变。这个过程本质上是一个数学归纳法。基础情况空列表时插入第一个人他前面没有其他人满足条件。归纳步骤在已有局面合法的情况下新插入的人满足自己的约束并且不破坏任何旧人的约束。由此最终结果合法。时间复杂度的分析也很清楚。排序部分为 O(n log n)。插入时ArrayList的add(index, element)方法需要把 index 之后的元素全部后移一位单次最坏 O(n)。总的时间复杂度是 O(n²)。空间复杂度主要是结果列表用了 O(n)。如果你用链表LinkedList插入确实可以到 O(1)但随机按下标访问第k个位置是 O(n)所以整体还是 O(n²)仅仅读写常数上可能有差异。4. 从低到高的空位法实现4.1 从低到高怎么建队列第二种思路和前面正好相反我们是按身高从低到高往空位里放人。这一招在很多“排序 贪心”题里也能用只是理解起来稍微抽象一点。假设我们先把所有人按身高从低到高排序然后一个一个放到最终数组的“空位”里。每个人在放入时因为前面已经放入的人都比他矮或等高但 k 小的先放所以已放入的人不会影响他的“高个子计数”。真正需要统计的是在这个人的最终位置上前方要预留几个空位给未来那些比他高的人。也就是说插入的时候我们从左往右数空位直接跳过已经占用的位置找到第k个空位把他放进去。这个“空位法”从另一个角度解释了同一道题也让我们对贪心结构理解得更深。4.2 空位法代码剖析假设按身高从低到高相同身高按 k 从大到小排序。为什么要相同身高按 k 从大到小因为在身高相同的一组里k 较大的人在最终队列中位置一定更靠后而空位法是从前往后数空位如果先放 k 较大的后放 k 较小的那后面的人插入时就不会把前面的人挤到不该有的位置反过来先放 k 小的再放 k 大的k 大的人就需要在已经占了的位置基础上再数后面的空位反而容易造成位置前移冲突。基于这个排序我们开一个长度为 n 的数组作为结果用“空位数量”来寻找插入位置。public int[][] reconstructQueue(int[][] people) { // 按身高从低到高身高相同k 从大到小 Arrays.sort(people, (a, b) - a[0] ! b[0] ? a[0] - b[0] : b[1] - a[1]); int n people.length; int[][] res new int[n][]; for (int[] p : people) { int pos 0; int empty p[1]; // 从前往后数 empty 个空位第 empty 个空位就是插入位置 while (empty 0 || res[pos] ! null) { if (res[pos] null) empty--; pos; } res[pos] p; } return res; }这段代码里要注意一个细节while判断里我写的是empty 0 || res[pos] ! null意思是只要没数够empty个空位就一直往前走如果数够了空位但当前位置已经被占也需要继续往后找下一个空位。实际效果是跳过所有已经有人占的格子数出第empty个空位并落到那里。这种写法虽然好理解但在时间上并不算最优。因为每插入一个人都要从数组头部开始扫描整体复杂度同样是 O(n²)。好处是占用的思考空间更贴近“先预留位置”的直觉对初学者理解空位思想很有帮助。4.3 两种思路对比两种方法的本质是一致的先把身高关系处理出一个单调顺序再利用“后来的人要么不影响我要么影响但不参与计数”的性质一次放置一个元素。从高到低插入法实现简单代码短面试时最推荐。它的逻辑链条是先放置高个子矮个子插队不会破坏高个子的 k 值因为矮个子不算作“不低于自己”。从低到高空位法更偏“构造”一些适合画图理解但代码里容易搞混空位计数和最终下标。我自己在讲解这道题时通常会先用从高到低的插入法把答案写出来然后再补一句“其实你也可以反过来从低到高用空位法理解”这样能把两种贪心视角都覆盖到。5. 常见问题与排查技巧实录5.1 排序规则写错导致的连锁问题这道题里最典型的错误就是把排序规则搞反。有人写成按身高升序、k 升序还有人把身高相同时 k 降序。一旦排序错误后面的插入过程大概率会输出一个看似有序、实际不满足约束的队列。排查这类问题时最好的办法是先跑题目自带的示例。如果示例没过不要急着调插入逻辑先打印排序后的数组验证排序规则是否正确。排序正确但结果错误再继续检查插入位置的下标是否从 0 开始、k是否被误减一。很多下标类问题都是0和1的边界没对齐导致的。5.2 相等身高插入时的小坑还有一批人会在处理身高相等元素时出问题。假如排序只按身高降序身高相同的两个元素的相对顺序不稳定那么插入后结果可能因测试用例不同而不同。比如[[7, 1], [7, 0]]排序后如果原顺序保持不变插入结果是[[7, 0], [7, 1]]这没问题。但如果你使用的排序算法不稳定且你恰好不处理 k 的升序最后就有可能出现错误结果。因此代码里务必显式写明h相同按k升序不要依赖排序算法的稳定性。5.3 一个完整的手推示例为了验证理解建议你在草稿纸上手动推一遍。我用题目给的输入演示整个插入序列。排序后[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]逐步插入插入[7, 0]列表为[[7, 0]]插入[7, 1]下标 1 插入列表为[[7, 0], [7, 1]]插入[6, 1]下标 1 插入列表为[[7, 0], [6, 1], [7, 1]]插入[5, 0]下标 0 插入列表为[[5, 0], [7, 0], [6, 1], [7, 1]]插入[5, 2]下标 2 插入列表为[[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]插入[4, 4]下标 4 插入列表为[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]对比发现最终结果和标准答案一致。这里每一步核心都是“只数当前队列前 k 个人”不需要关心后面的人。5.4 常见问题速查问题现象常见原因处理方式排序后仍结果错误身高相同时未按 k 升序排序将排序规则补全不要省略相等条件下的排序插入后人员计数不对把 k 当作绝对位置而不是相对位置插入下标必须用当前列表的长度内的下标不能直接当最终数组下标使用数组时越界从高到低插入法直接对固定数组插入使用可扩容的 List或先确定最终位置再放从低到高空位法结果错乱同身高 k 的排序方向搞反从低到高时应按 k 降序保证先放靠后的人结果为空或有 nullJava 数组未初始化就使用对新数组先填充完所有元素再做转换这几种错误我在和同行交流时发现所有人都至少踩过其中一种。尤其是排序补全规则几乎属于“答案里一句话的事但自己写时很容易漏”的类型。6. 做题过程中的几点体会与扩展应用整理这道题的过程里我自己最大的收获并不是那道题本身的代码而是它训练出来的思维模式。以后看到类似题目我会先问自己如果把元素按某个维度排序能不能让后面的处理不改变前面的结果如果存在这样一个排序维度那就非常适合贪心。比如经典的会议室安排、任务调度、区间覆盖都和这种“预处理顺序 一次扫描决策”的结构相似。区别在于有的贪心决策是“选或不选”有的则是“插到哪个位置”。LC406 属于后者而且因为多了一个身高维度排序规则需要仔细定义。这道题还有一个很好的变体如果把每个人改成[身高, 后面不低于自己的人数]解题策略又该如何变化你可以试着分析一下。思路其实类似只是顺序方向反转过来从后往前处理可能更合适。能把这道题的原型彻底吃透再去做这些变体基本就是举一反三的事。再聊一点刷题习惯。很多人看到贪心标签就直接默认用贪心但一旦结果错了就不知道问题在哪。我的经验是贪心题必须做两件事想清楚排序规则的直觉理由再用手推的小样例验证一两遍。LC406 本身不太会出现大规模超时大部分人错在规则而不是复杂度所以手推一遍样例比闷头调试代码更高效。最后给一个建议如果面试时被问到这道题尽量把两种解法都提一下。先讲从高到低插入法的直觉高个子先排好矮个子后面插进来不影响已经排好的高个子。再补充一句也可以用升序 空位法理解。面试官往往会追问一句“为什么插入位置是 k”如果你能提到“因为当前队列里所有已放置的人都比他高或和他一样高”这个问题基本就稳了。