1. 从一道题看贪心与排序的配合逻辑Leetcode 406 这道题标题叫“根据身高重建队列”乍一看像是数据结构题实际上它是一道非常典型的排序 贪心 插入的综合题。我当年第一次做的时候第一反应是“这题是不是得用拓扑排序”后来发现完全想复杂了。它真正考察的是你能不能从两个维度身高、前面比他高的人数里找到一个合理的处理顺序把复杂问题拆成一步步可操作的简单动作。这道题在实际面试里出现的频率不算特别高但它的思想非常值得琢磨。很多做过后端开发或者算法岗的朋友应该都有体会工作中经常遇到“多条件约束下的排序与重建”问题比如任务调度、优先级队列构建、依赖关系整理等等。406 这道题就是一个极简版的模型每个人有两个属性(h, k)h是身高k是排在他前面且身高大于等于他的人的数量。给你一个打乱的数组让你重建出满足所有k条件的队列。适合谁来参考这篇内容如果你正在刷 Leetcode尤其是刚接触贪心类题目或者对“为什么先排身高高的”这个点一直没想透那这篇会帮你把思路彻底理顺。如果你已经做过这道题但只是背了代码我也建议你看看后面的实操细节和排查技巧因为这道题在 C 语言实现里有几个坑不踩一次很难记住。提示这道题的核心关键词是“身高降序、k 升序”以及“按 k 插入”。记住这两个点代码就不会写偏。2. 题目拆解与核心思路选型2.1 两个维度的约束到底该怎么处理题目给的是people[i] [hi, ki]表示第 i 个人的身高是hi前面有ki个身高大于等于hi的人。注意这里是“大于等于”不是“大于”这个细节很关键后面会影响到排序时对相同身高的处理。很多人一开始会想我能不能同时考虑两个维度比如先按身高升序排再按 k 升序排我试过不行。因为如果你先处理矮的人矮的人前面有多少个高的人这件事会受到后面插入的高的人的影响你根本没法确定位置。换句话说矮的人的位置依赖于高的人怎么排但高的人的位置不依赖于矮的人。这就引出了一个非常重要的思路先处理确定性高的部分再处理确定性低的部分。身高最高的人他前面比他高的人数量一定是 0因为没人比他高所以他的 k 值直接决定了他站在第几个位置。而矮的人他前面可能有高的人也可能有同样高的人位置会受到后续插入的影响。所以正确的处理顺序是按身高从高到低排序身高相同的按 k 从小到大排序。然后依次把每个人插入到队列中索引为 k 的位置。2.2 为什么身高相同要按 k 升序这个问题我当初也卡了一下。假设有两个人身高都是 180一个 k0一个 k1。如果按 k 降序排先处理 k1 的人他插入到索引 1 的位置队列变成[空, 180(k1)]。然后再处理 k0 的人他插入到索引 0队列变成[180(k0), 180(k1)]。看起来好像也对但问题在于当后面有更矮的人插入时如果相同身高的人顺序不对会导致矮的人计算“前面有多少个大于等于自己的人”时出现偏差。具体来说如果 k 大的排前面那么 k 小的人插入时会被挤到后面最终可能导致某个矮的人前面实际比他高的人数量和他自己的 k 不匹配。我举个更直观的例子。假设排序后是[180(k1), 180(k0)]先插入 k1 的人到索引 1队列是[_, 180]。再插入 k0 的人到索引 0队列是[180, 180]。这时候看起来没问题。但如果后面来了一个 170(k2) 的人他插入到索引 2队列变成[180, 180, 170]。170 前面有两个 180满足 k2。但如果相同身高的人顺序反了在某些边界情况下会导致插入位置计算错误。更严谨的解释是当身高相同时k 小的人应该排在前面因为他的 k 值更小意味着他前面比他高的人更少。如果先插入 k 大的人他占据了靠前的位置后面 k 小的人插入时会把 k 大的人往后挤导致 k 大的人前面实际比他高的人数量减少违反了他的 k 条件。所以必须按 k 升序处理保证 k 小的人先占据靠前的位置k 大的人后插入时自然被挤到后面前面比他高的人数量刚好等于他的 k。2.3 插入操作为什么用动态数组而不是链表在 C 语言里插入操作如果用手写链表代码会非常长而且容易出错。用动态数组也就是手动模拟 vector反而更简单。因为这道题的数据规模通常不大Leetcode 上 n 最多 2000 左右每次插入最坏 O(n)总时间复杂度 O(n²)完全够用。我实测过用动态数组实现代码量大概 60 行左右逻辑清晰调试也方便。如果用链表光是节点定义、插入、遍历就要多写 30 行而且链表在按索引插入时还需要先遍历到指定位置并没有性能优势。所以我的建议是老老实实用数组别炫技。注意C 语言里没有现成的 vector需要自己维护一个数组和当前长度。插入时从后往前搬移元素腾出位置后再赋值。3. C 语言实现的核心细节与实操要点3.1 排序函数的写法与比较逻辑C 语言标准库里的qsort是这道题排序环节的首选。它的原型是void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));对于people数组每个元素是int*也就是指向长度为 2 的整型数组的指针。所以比较函数接收的是const void*实际指向的是int**。比较逻辑如下int cmp(const void *a, const void *b) { int *p1 *(int **)a; int *p2 *(int **)b; if (p1[0] ! p2[0]) { return p2[0] - p1[0]; // 身高降序 } return p1[1] - p2[1]; // k 升序 }这里有个细节p2[0] - p1[0]是降序因为如果 p1 身高大于 p2结果是负数qsort 会把 p1 排在前面。很多人容易写成p1[0] - p2[0]那就变成升序了整个逻辑就反了。另外返回值用减法而不是比较运算符是因为减法在整数范围内不会溢出身高和 k 都是正数差值在 int 范围内而且写法简洁。但如果你不确定数据范围用(p2[0] p1[0]) ? 1 : -1这种写法更稳妥。3.2 动态数组的插入操作详解插入操作是这道题的核心。假设我们已经排好序现在要依次把每个人插入到结果数组中。结果数组用int **res表示当前长度为len。对于第 i 个人他的 k 值是people[i][1]我们要把他插入到res的索引k位置。插入步骤如下从res的末尾开始把索引k到len-1的元素全部往后搬一位。把people[i]放到索引k的位置。len加一。用代码表示for (int i 0; i n; i) { int k people[i][1]; for (int j len; j k; j--) { res[j] res[j - 1]; } res[k] people[i]; len; }这里res数组需要预先分配足够的空间至少n个元素。因为每个人最终都会被插入一次所以res的大小就是n。提示搬移元素时一定要从后往前搬如果从前往后搬会把后面的元素覆盖掉。这是插入操作的基本功但我在面试里见过不少人写反。3.3 内存分配与返回值处理Leetcode 的 C 语言题目通常要求返回数组和数组长度。函数签名一般是int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes);我们需要分配res数组以及每个元素的列大小数组。returnColumnSizes是一个指向指针的指针需要分配peopleSize个 int每个都设为 2。returnSize设为peopleSize。完整的内存分配代码int **res (int **)malloc(sizeof(int *) * peopleSize); *returnColumnSizes (int *)malloc(sizeof(int) * peopleSize); for (int i 0; i peopleSize; i) { (*returnColumnSizes)[i] 2; } *returnSize peopleSize;注意这里没有为每个res[i]单独分配内存因为我们是直接复用people数组里的指针。这样做的好处是省内存坏处是如果后续修改了res[i]指向的内容会影响到原数组。但在这道题里我们只是重新排列指针不修改内容所以没问题。如果你担心指针复用带来的潜在风险也可以为每个元素单独 malloc 一个长度为 2 的数组然后把people[i][0]和people[i][1]拷贝进去。但这样代码会多几行而且需要额外释放内存。我个人的习惯是直接复用简洁高效。4. 完整实操流程与代码逐段解析4.1 从输入到输出的完整步骤假设输入是people [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]我们一步步走一遍。第一步排序。按身高降序身高相同按 k 升序。排序后的结果是[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]第二步依次插入。插入[7,0]到索引 0res [[7,0]]插入[7,1]到索引 1res [[7,0], [7,1]]插入[6,1]到索引 1res [[7,0], [6,1], [7,1]]插入[5,0]到索引 0res [[5,0], [7,0], [6,1], [7,1]]插入[5,2]到索引 2res [[5,0], [7,0], [5,2], [6,1], [7,1]]插入[4,4]到索引 4res [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]最终结果就是[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。你可以验证一下对于[5,0]前面没有比他高或相等的人k0 正确。对于[7,0]前面只有[5,0]比他矮所以比他高的人数是 0k0 正确。对于[5,2]前面有[7,0]和[7,1]两个比他高的人k2 正确。其他同理。4.2 完整代码实现与注释#include stdlib.h int cmp(const void *a, const void *b) { int *p1 *(int **)a; int *p2 *(int **)b; if (p1[0] ! p2[0]) { return p2[0] - p1[0]; // 身高降序 } return p1[1] - p2[1]; // k 升序 } int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) { // 排序 qsort(people, peopleSize, sizeof(int *), cmp); // 分配结果数组 int **res (int **)malloc(sizeof(int *) * peopleSize); *returnColumnSizes (int *)malloc(sizeof(int) * peopleSize); for (int i 0; i peopleSize; i) { (*returnColumnSizes)[i] 2; } *returnSize peopleSize; // 依次插入 int len 0; for (int i 0; i peopleSize; i) { int k people[i][1]; for (int j len; j k; j--) { res[j] res[j - 1]; } res[k] people[i]; len; } return res; }这段代码在 Leetcode 上可以直接通过。时间复杂度是 O(n²)空间复杂度是 O(n)。对于 n2000 的数据规模运行时间在几毫秒以内完全没问题。4.3 参数选择与边界情况处理有几个边界情况需要特别注意n0题目通常保证 n≥1但如果你要写健壮的代码可以在开头判断if (peopleSize 0) { *returnSize 0; return NULL; }。k 值等于当前长度比如插入[4,4]时当前len5k4插入到索引 4相当于追加到末尾。搬移循环for (j len; j k; j--)会执行一次把res[4]搬到res[5]然后res[4]赋值为新元素。逻辑正确。k 值大于当前长度理论上不会发生因为排序后 k 值一定小于等于当前已插入的人数。但如果你不放心可以加一个断言或者取k k len ? k : len。注意qsort的比较函数里不要用p1[0] - p2[0]做降序也不要用p2[1] - p1[1]做升序方向搞反了结果就全错了。我建议写完排序后先打印一下排序结果确认顺序正确再继续写插入逻辑。5. 常见问题与排查技巧实录5.1 排序后结果不对怎么办这是最常见的问题。症状是最终队列里某些人的 k 条件不满足。排查步骤在qsort之后加一个循环打印排序后的people数组。正确的顺序应该是身高从大到小身高相同的 k 从小到大。检查比较函数里的减法方向。身高降序是p2[0] - p1[0]k 升序是p1[1] - p2[1]。如果写反了排序结果会完全相反。检查qsort的第三个参数是不是sizeof(int *)。因为people是int**每个元素是int*所以大小是指针的大小不是sizeof(int) * 2。我当初就犯过第三个错误写成了sizeof(int) * 2结果排序时内存访问错乱程序直接崩溃。后来改成sizeof(int *)就对了。5.2 插入后结果数组元素错位症状是最终结果里某些元素重复或者丢失。原因通常是搬移循环写错了。正确的搬移是从后往前for (int j len; j k; j--) { res[j] res[j - 1]; }如果你写成for (int j k; j len; j)那就是从前往后搬会把res[k]覆盖掉导致元素丢失。这个错误很隐蔽因为程序不会崩溃只是结果不对。另一个可能的原因是len没有正确递增。每次插入后必须len否则下一次插入时搬移范围会出错。5.3 内存泄漏与释放问题Leetcode 的 C 语言题目通常不需要你释放内存因为评测系统会统一回收。但如果你在本地测试记得释放res和*returnColumnSizes。不过要注意res里的每个元素是指向people数组里的指针不能单独 free否则会重复释放。如果你在本地写测试代码可以这样释放free(res); free(*returnColumnSizes); // people 数组由调用者释放但如果你在reconstructQueue里为每个res[i]单独 malloc 了内存那就需要先 free 每个res[i]再 freeres。这就是复用指针和拷贝内容的区别选择哪种方式取决于你的需求。5.4 常见问题速查表问题现象可能原因排查方法解决方案排序结果与预期相反比较函数减法方向写反打印排序后数组身高降序用p2[0]-p1[0]k 升序用p1[1]-p2[1]程序崩溃或乱码qsort元素大小参数错误检查第三个参数应为sizeof(int *)结果元素丢失或重复搬移循环方向错误检查for循环的起止和方向从后往前搬for (jlen; jk; j--)某些人 k 条件不满足相同身高排序顺序错误检查身高相同时是否按 k 升序比较函数中身高相同时返回p1[1]-p2[1]结果数组长度不对len未正确递增检查每次插入后是否len插入后立即len提示如果你在面试中遇到这道题写完代码后一定要手动跑一个简单例子比如[[7,0],[7,1]]确认输出是[[7,0],[7,1]]而不是[[7,1],[7,0]]。这个例子能快速验证排序和插入逻辑是否正确。5.5 独家避坑技巧我在多次练习和教学中总结了几个小技巧能帮你少走弯路先写排序再写插入。不要试图一次性写完整个函数分两步调试。排序写完后打印验证确认无误再写插入。用纸笔模拟小规模数据。对于 n3 或 n4 的情况手动模拟一遍插入过程比盯着代码看有效得多。注意 k 的含义是“大于等于”。这意味着身高相同的人也会被计入 k。所以排序时身高相同的必须按 k 升序否则相同身高的人之间会互相影响。不要用链表。我见过有人为了“优雅”用链表实现结果调试了两个小时。数组虽然看起来笨但逻辑简单不容易出错。Leetcode 的 C 语言环境不支持变长数组VLA。如果你写int res[n][2]可能会编译错误。老老实实用malloc。6. 从这道题延伸出的通用解题框架6.1 多维度排序问题的通用处理模式406 这道题其实代表了一类问题给定一组带多个属性的元素要求按照某种约束重新排列。这类问题的通用解法是确定处理顺序找到一个维度使得按这个维度排序后元素的处理顺序是确定的不会因为后续操作而改变。确定插入规则对于每个元素根据其属性计算它在结果中的位置。验证约束确保插入后所有元素的约束条件都满足。在 406 里身高就是那个“确定处理顺序”的维度因为高的人不受矮的人影响。k 值就是“插入规则”直接决定插入位置。类似的题目还有“根据身高重建队列”的变种比如“根据分数排名重建列表”、“根据依赖关系重建任务顺序”等。核心思想都是一样的先处理不受影响的部分再处理受影响的部分。6.2 贪心策略的适用条件与验证方法贪心算法不是万能的它需要满足两个条件贪心选择性质和最优子结构。在 406 里贪心选择性质体现在每次插入当前最高的人时他的位置是确定的不需要考虑后面的人。最优子结构体现在插入完前 i 个人后前 i 个人的相对顺序已经满足约束后续插入不会破坏这个约束。验证贪心策略是否正确可以用“交换论证法”假设存在一个最优解如果它和贪心解在某一步不同尝试交换两个元素证明交换后不会变差。在 406 里如果你把两个身高不同的人交换身高高的人会被放到后面导致他的 k 条件不满足所以贪心解是最优的。6.3 时间复杂度优化空间O(n²) 的时间复杂度对于 n2000 来说完全够用但如果 n 达到 10^5就需要优化了。优化的方向是用树状数组或线段树维护空位每次插入时二分查找第 k 个空位时间复杂度可以降到 O(n log n)。不过这个优化在面试里通常不需要除非面试官明确要求。我个人的建议是先把 O(n²) 的解法写对、写清楚再考虑优化。很多人在面试里为了追求最优解结果基础解法都写错了反而得不偿失。6.4 类似题目的举一反三如果你掌握了 406 的思路可以尝试以下变种变种一k 的定义改为“前面比他矮的人的数量”。这时候处理顺序就要反过来先处理矮的人。变种二每个人有三个属性比如身高、体重、k 值。这时候需要先确定哪个属性是主排序维度。变种三要求输出所有满足条件的队列而不是任意一个。这时候就需要回溯或动态规划了。这些变种在面试里偶尔会出现但核心思想不变找到确定性最高的维度先处理它再逐步处理其他维度。7. 个人实操体会与最后分享这道题我前前后后做过五六遍每次都有新的体会。最开始是背代码后来是理解思路再后来是能给别人讲清楚为什么这么写。我觉得这道题最大的价值不在于它本身有多难而在于它教会你一种思维方式面对多约束问题不要试图同时解决所有约束而是找到约束之间的依赖关系从确定性最高的部分入手逐步推进。这个思维方式在后端开发里非常有用。比如做任务调度系统时有些任务有前置依赖有些没有你就可以先调度没有依赖的任务再逐步处理有依赖的。又比如做数据库索引设计时多个查询条件有优先级你可以先按选择性最高的条件过滤再逐步细化。最后再分享一个小技巧如果你在面试里遇到这道题可以先口头描述思路确认面试官认可后再写代码。这样即使代码有小 bug面试官也会因为你思路清晰而给你加分。我见过太多人上来就写代码结果写到一半发现思路错了再改就来不及了。另外C 语言实现时记得包含stdlib.h因为qsort和malloc都在这个头文件里。如果你用的是 Leetcode 的在线编辑器它通常会自动包含常用头文件但本地编译时别忘了加。这个细节虽小但关键时刻能省你几分钟的调试时间。