题目描述
思路解析
一句话答案：LeetCode 406 根据身高重建队列的经典解是贪心排序加插入：按身高从高到矮排序（同高时 k 小的在前），再把每个人插到结果数组的下标 k 处。先放的人都不比后来者矮，矮个子插队不影响已放好的 k，一遍插完即得答案。数组中间插入 O(n)，整体时间 O(n²)、空间 O(n)。
根据身高重建队列到底在问什么
每个人用一对数 [h, k] 描述：h 是身高，k 是「排在他前面、身高大于等于 h 的人数」。输入是被打乱的一组人，要求重新排出一支队伍，使队伍里每个人的 k 都与实际站位吻合。注意 k 数的不是「前面所有人」，而只数「前面身高不低于自己的人」——比自己矮的人站在前面多少个都不影响 k。这个不对称正是解题的突破口。
为什么贪心要按身高从高到矮排序
直觉的做法是枚举排列逐一验证，n 个人有 n! 种排法，完全不可行。换个角度问：谁的位置最容易先定下来？答案是最高的人——他的 k 只受同样高或更高的人影响，而比他矮的人对他完全「透明」。
于是贪心策略成形：按身高从高到矮逐个安排。轮到某个人时，已经放进队列的全是身高不小于他的人，还没放的全比他矮。后面来的矮个子无论插到哪，都不会被已放好的人「数进」自己的 k 里，所以先定下来的位置永远不会被推翻——这就是这个贪心不需要回头修改的原因。
同样身高时为什么 k 小的要排在前面
身高相同的两个人会互相计入对方的 k：站在后面的那位，前面多了一个「身高等于自己」的人。既然 k 小意味着前面这样的人更少，k 小的就必须站在 k 大的前面。排序时把同身高按 k 升序排，先插 k 小的，后插的同高者落在其后，两人的相对顺序自然正确。如果反过来按 k 降序排，先插进去的 k 大者会被后插的同高者挤到错误的位置上。
为什么每个人恰好插到下标 k 就是对的
轮到 [h, k] 入队时，队列里现有的人身高全都大于等于 h。把他插到下标 k，意味着他前面恰好有 k 个人，而这 k 个人个个身高不低于他——他的 k 当场成立，一位不多一位不少。插到末尾、或凭感觉加个偏移量都不行：队列里此刻没有比他矮的人，下标就是精确的计数。
拿题目示例验证：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]，排序后依次是 [7,0]、[7,1]、[6,1]、[5,0]、[5,2]、[4,4]，各自插到下标 0、1、1、0、2、4，得到 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]，与标准答案一致。
复杂度是多少，还能不能更快
排序 O(n log n)；瓶颈在插入——往数组中间插一个元素要把后面的整体右移，最坏 O(n)，n 次插入合计 O(n²)，这也是整体时间复杂度。空间 O(n)，用于存放结果队列。
想更快可以把「插到第 k 个空位」交给树状数组或线段树维护空位的前缀和，每次二分定位第 k 个空位并占掉，降到 O(n log n)。面试中先讲清 O(n²) 的贪心与正确性论证，被追问再谈这层优化即可。最常见的翻车点有两个：身高排成升序（矮的先放，后来的高个子会改变其 k 的计数，全盘皆错），以及同身高时把 k 排成降序。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
抓两点：先处理高的人（高的人只看更高的人，干扰最少）；同样高的先放 k 小的（保证 k 小的排在前面）。排好序后，每个人「插到第 k 位」就是答案——这就是这道题最漂亮的地方。
这是题目给的乱序输入（每格是一个人 "身高,k"）。贪心的第一步永远是排序——按身高从高到矮，身高相同就让 k 小的排前面。下一帧看排好序长什么样。
排好序了（数组重排成这一行）：身高从高到矮 7,7,6,5,5,4；两个 7 里 k 小的 [7,0] 在前。排序是整个贪心的地基。下面开始逐个「插队」，每插一个就看队伍怎么长出来。
蓝色光标停在 [7,0]。关键一步：此刻队列里已经放好的人，身高全都 ≥ 7（因为我们是从高到矮处理的）。所以他的 k=0 直接告诉我们落点——插到下标 0，让前面恰好 0 个比他高（或一样高）的人。
数落点：当前队列长度 0，要插到下标 0。意味着原来在下标 0 及之后的人，都向右挪一格，给 [7,0] 腾位。灰色是已放置、即将被挤动的人。
把 [7,0] 插入到下标 0，队列长出一节：[[7,0]]。绿色高亮的是已经放进队列的人。后面再来的都比他矮，矮个子谁也不会被他「数进」k 里，所以他这个坑位是稳的。
蓝色光标停在 [7,1]。关键一步：此刻队列里已经放好的人，身高全都 ≥ 7（因为我们是从高到矮处理的）。所以他的 k=1 直接告诉我们落点——插到下标 1，让前面恰好 1 个比他高（或一样高）的人。
数落点：当前队列长度 1，要插到下标 1。意味着原来在下标 1 及之后的人，都向右挪一格，给 [7,1] 腾位。灰色是已放置、即将被挤动的人。
把 [7,1] 插入到下标 1，队列长出一节：[[7,0], [7,1]]。绿色高亮的是已经放进队列的人。后面再来的都比他矮，矮个子谁也不会被他「数进」k 里，所以他这个坑位是稳的。
蓝色光标停在 [6,1]。关键一步：此刻队列里已经放好的人，身高全都 ≥ 6（因为我们是从高到矮处理的）。所以他的 k=1 直接告诉我们落点——插到下标 1，让前面恰好 1 个比他高（或一样高）的人。
数落点：当前队列长度 2，要插到下标 1。意味着原来在下标 1 及之后的人，都向右挪一格，给 [6,1] 腾位。灰色是已放置、即将被挤动的人。
把 [6,1] 插入到下标 1，队列长出一节：[[7,0], [6,1], [7,1]]。绿色高亮的是已经放进队列的人。后面再来的都比他矮，矮个子谁也不会被他「数进」k 里，所以他这个坑位是稳的。
蓝色光标停在 [5,0]。关键一步：此刻队列里已经放好的人，身高全都 ≥ 5（因为我们是从高到矮处理的）。所以他的 k=0 直接告诉我们落点——插到下标 0，让前面恰好 0 个比他高（或一样高）的人。
数落点：当前队列长度 3，要插到下标 0。意味着原来在下标 0 及之后的人，都向右挪一格，给 [5,0] 腾位。灰色是已放置、即将被挤动的人。
把 [5,0] 插入到下标 0，队列长出一节：[[5,0], [7,0], [6,1], [7,1]]。绿色高亮的是已经放进队列的人。后面再来的都比他矮，矮个子谁也不会被他「数进」k 里，所以他这个坑位是稳的。
蓝色光标停在 [5,2]。关键一步：此刻队列里已经放好的人，身高全都 ≥ 5（因为我们是从高到矮处理的）。所以他的 k=2 直接告诉我们落点——插到下标 2，让前面恰好 2 个比他高（或一样高）的人。
数落点：当前队列长度 4，要插到下标 2。意味着原来在下标 2 及之后的人，都向右挪一格，给 [5,2] 腾位。灰色是已放置、即将被挤动的人。
把 [5,2] 插入到下标 2，队列长出一节：[[5,0], [7,0], [5,2], [6,1], [7,1]]。绿色高亮的是已经放进队列的人。后面再来的都比他矮，矮个子谁也不会被他「数进」k 里，所以他这个坑位是稳的。
蓝色光标停在 [4,4]。关键一步：此刻队列里已经放好的人，身高全都 ≥ 4（因为我们是从高到矮处理的）。所以他的 k=4 直接告诉我们落点——插到下标 4，让前面恰好 4 个比他高（或一样高）的人。
数落点：当前队列长度 5，要插到下标 4。意味着原来在下标 4 及之后的人，都向右挪一格，给 [4,4] 腾位。灰色是已放置、即将被挤动的人。
最后一个人 [4,4] 插到下标 4，队伍补全为 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。整支队伍每个人的 k 都成立——重建完成。
全部插完，答案 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。可以挑一个验证：比如 [6,1]，它前面是 [5,0]、[7,0]，其中身高 ≥6 的只有 [7,0] 一个 → 正好 k=1，成立。先排高、再按 k 插入，一次成型。
边界都顺着同一套规则：先降序排身高、同高按 k 升序，再逐个插到下标 k，单人/全 k=0/同身高都能一把过。
两个高频追问：矮个子不进 k 的统计所以不破坏已定位置；想从 O(n²) 提速就用线段树找第 k 个空位。
参考代码
def reconstructQueue(people): # 身高降序；同高时 k 升序 people.sort(key=lambda p: (-p[0], p[1])) queue = [] for p in people: queue.insert(p[1], p) # 插到下标 k return queue复杂度
- 时间：O(n²)，排序 O(n log n)，但逐个 insert 到数组中间最坏 O(n)，共 n 次 → O(n²) 主导
- 空间：O(n)，结果队列存 n 个人（排序若原地则不算额外）
易错点
面试追问把动画讲成自己的话
追问为什么后插入的人不会破坏前面已确定的人的 k？
追问插入是 O(n)，能优化吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题