LeetCode 406. 根据身高重建队列

2022-04-24 HGNULB 约 9 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 406. 根据身高重建队列

题意分析

给一组打乱顺序的人，每个人用 [h, k] 描述：h 是身高，k 是「排在他前面、且身高大于等于 h 的人数」。要求还原出一个满足所有人 k 值的队列。题目保证答案一定存在。

最容易读错的是 k 的定义。它统计的是「前面」的人，不是全队；它的比较是「大于等于」而不是「大于」，所以同身高的人之间会互相计数；它只关心人数，不关心那些人具体是谁、站在哪。这三点合起来给出一个很强的信号：一个人的 k 值完全不受比他矮的人影响——比他矮的人无论插在他前面还是后面，都不会被计入他的 k。

这条「矮的人对高的人无影响」的单向性，是整道题的题眼。它意味着人与人之间存在一个可以逐步确定的顺序：如果先把所有更高的人安排妥当，那么后面再往队列里塞矮的人时，前面那些人的 k 依然成立。反过来若先安排矮的人，后来插进一个高个子就会把某些人的 k 全部撑大，之前的努力作废。

数据规模只到 1000 人，$O(n^2)$ 的做法完全能过，这个宽松的上界暗示不必上树状数组之类的高级结构。

边界：只有一个人时答案就是它自己，且 k 必然为 0；可能存在多个人身高完全相同；k 的取值范围保证不会超过比他高的人数，所以插入位置一定合法。

解法：身高降序排序后按 k 插入

核心思路

暴力做法是枚举全排列再逐个验证 k，$O(n! \cdot n)$，一眼不可行。稍好一点的想法是「每次从剩下的人里找一个可以放在队首的人」，但每一步都要重新统计，写起来既繁又慢。瓶颈在于：所有人的约束互相纠缠，看不出该先确定谁。

解开纠缠的正是上面那条单向性——矮的人不影响高的人。既然影响是单向的，那就按身高从高到矮依次安排，这样每个人被放置时，队列里已有的人全都不矮于他，他的 k 可以当场算准且以后不会再变。

于是有了这条不变量：处理完前若干个人后，结果列表里的这些人，其相对顺序已经满足他们各自的 k 值，并且后续插入的任何人都不会破坏它。 前半句靠插入位置的选择保证，后半句靠「后插入的人身高不大于已有的人，永远不会被计入他们的 k」保证。

插入位置怎么选？当前要放的人 [h, k]，此刻结果列表里全是身高 ≥ h 的人，所以「排在他前面的人数」就等于「身高 ≥ h 且排在他前面的人数」。要让这个数恰好是 k，把他插到下标 k 处即可——下标 k 前面正好有 k 个元素。

还剩一个细节：同身高的人怎么排？同身高之间是互相计数的（≥ 含等号），所以 k 小的必须排在 k 大的前面。如果同身高按 k 降序处理，先插入的 k 大的人会被后插入的 k 小的人挤到后面，导致它的 k 反而变小。所以排序规则必须是身高降序、同身高 k 升序。这样同身高的人依次插入时，后来者的下标一定不小于前者，不会互相顶位。

解题步骤

排序：身高降序，身高相同则 k 升序。降序是为了让「已放置的人都不矮于当前人」成立，这是插入位置能直接取 k 的前提；同身高 k 升序是为了让同一批人之间不互相顶位。两条规则缺一不可，且都必须写进比较器——比较器不覆盖相等情形时，不同语言、不同 JDK 版本的排序结果可能不同，答案随之飘移。

准备一个可以按下标插入的结果容器：Java 用 ArrayList（add(index, e) 会把后面的元素整体后移），Go 里没有现成的插入 API，所以先 append 一个占位再用 copy 把 [idx, len-1) 整段右移一位，最后写入 idx。两种写法语义相同。

按排序后的顺序遍历，把每个人插到下标 person[1]（即 k）处：这一步是全题的核心。插到下标 k 意味着他前面恰好 k 个人，而这些人此刻全都不矮于他，正好满足定义。不需要跳过任何人，也不需要检查位置是否合法——题目保证答案存在，等价于保证 k 不超过当前列表长度。

注意插入会让后面所有人整体后移，但这不会破坏他们的 k：被挤后的人前面多了一个身高不大于他们的新人，而这种人不计入 k，所以他们的 k 依旧成立。这正是不变量的后半句在起作用。

遍历结束后转成二维数组返回：Java 里 toArray(new int[n][2]) 直接得到 int[][]；Go 里结果切片本身就是 [][]int。

以 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]]）。

排序后得到 [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]：身高 7、6、5、4 依次递减，两个身高 7 的按 k 升序排成 0、1，两个身高 5 的按 k 升序排成 0、2。

插入 [7,0] 到下标 0：[[7,0]]。

插入 [7,1] 到下标 1：[[7,0], [7,1]]。它前面有一个身高 7 的人，k = 1 成立。若这里同身高按 k 降序排序，[7,1] 会先被插到下标 1（越界或补到末尾），随后 [7,0] 插到下标 0 把它挤到下标 2，k 就错了。

插入 [6,1] 到下标 1：[[7,0], [6,1], [7,1]]。它前面有一个人（身高 7），k = 1 成立；被挤到后面的 [7,1] 前面多了个身高 6 的矮子，不计入它的 k，仍然成立。

插入 [5,0] 到下标 0：[[5,0], [7,0], [6,1], [7,1]]。它前面 0 个人，k = 0 成立；后面三个人前面各多了一个身高 5 的矮子，k 全部不受影响。

插入 [5,2] 到下标 2：[[5,0], [7,0], [5,2], [6,1], [7,1]]。它前面是 [5,0] 和 [7,0]，两个都不矮于 5，k = 2 成立。

插入 [4,4] 到下标 4：[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。它前面 4 个人，身高分别是 5、7、5、6，全部 ≥ 4，k = 4 成立。

遍历结束，返回该列表，与期望输出一致。

代码实现

class Solution {
    // 对身高降序排序，同身高按 k 升序排序，可以保证插入当前人时，结果中已有的人都不矮于他。
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (first, second) -> {
            if (first[0] != second[0]) {
                return Integer.compare(second[0], first[0]);
            }
            return Integer.compare(first[1], second[1]);
        });

        List<int[]> res = new ArrayList<>();
        for (int[] person : people) {
            res.add(person[1], person);
        }

        return res.toArray(new int[people.length][2]);
    }
}

func reconstructQueue(people [][]int) [][]int {
    // 对身高降序排序，同身高按 k 升序排序，可以保证插入当前人时，结果中已有的人都不矮于他。
    sort.Slice(people, func(i, j int) bool {
        if people[i][0] != people[j][0] {
            return people[i][0] > people[j][0]
        }
        return people[i][1] < people[j][1]
    })

    res := make([][]int, 0, len(people))
    for _, person := range people {
        idx := person[1]
        res = append(res, nil)
        copy(res[idx+1:], res[idx:])
        res[idx] = person
    }

    return res
}

复杂度分析

时间复杂度：$O(n^2)$，其中 n 是人数。凭什么：排序是 $O(n \log n)$，但每次按下标插入都要把后面的元素整体后移，单次最坏 $O(n)$，n 次插入合计 $O(n^2)$，插入这一项占主导。n ≤ 1000 时约百万次移动，完全可以接受。

空间复杂度：$O(n)$。凭什么：结果列表要存下全部 n 个人；排序在原数组上进行（Java 的 Arrays.sort 对对象数组用归并需要 $O(n)$ 辅助空间，量级相同），没有递归深度超过对数的结构。

关键点总结

约束互相纠缠时，先找「影响是单向的」那个维度，沿着它从「不受影响的一端」开始逐个确定——这是贪心构造类问题最通用的破题手法，比记住「先排高的」这个结论更有迁移价值。

排序规则不是随便定的，两条规则各自对应一条正确性论证：身高降序保证「已放置者都不矮于当前人」，同身高 k 升序保证「同批次不互相顶位」。面试时要能分别说清这两句话。

「插到下标 k」之所以成立，是因为此刻列表里的人全部满足计数条件，于是「前面的人数」和「前面不矮于他的人数」这两个量重合了——把复杂条件化归成简单下标，是构造题里常见的一步。

后插入的元素会把已有元素整体后移，却不破坏它们的正确性，这条不变量必须主动验证；很多人写对了代码却讲不出为什么后移是安全的，追问时就答不上来。

数据范围 n ≤ 1000 明确允许 $O(n^2)$；若把上界提到 $10^5$，就需要用树状数组或线段树在 $O(n \log n)$ 内找「第 k + 1 个空位」——能顺口点出这个升级路径是加分项。

易错点总结

身高按升序排序：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 时先放 [4,4]，下标 4 处根本没有位置（列表还是空的），Java 抛 IndexOutOfBoundsException。

同身高按 k 降序排序：[[7,0],[7,1]] 会先插 [7,1] 再插 [7,0]，后者插到下标 0 把前者挤到下标 1，结果 [7,1] 前面只有一个人却本该有一个——顺序反了以后同身高之间的相对次序整体倒置，k 全错。

比较器只写身高不处理相等情形：[[5,0],[5,2]] 的相对顺序由排序算法的稳定性决定，Java 的 Arrays.sort 对对象数组稳定而 Go 的 sort.Slice 不稳定，同一份输入两种语言给出不同答案。

插入位置用 person[0]（身高）而不是 person[1]（k）：[[7,0]] 会试图插到下标 7，列表长度为 0，直接越界崩溃。

用固定长度数组 + 直接下标赋值代替插入：[[7,0],[7,1],[6,1]] 中 [6,1] 会覆盖掉 [7,1] 所在的位置，丢人。

Go 里忘记先 append 占位就 copy：copy(res[idx+1:], res[idx:]) 在切片长度不足时只复制 0 个元素，[[7,0],[7,1]] 处理完长度仍为 1，最终返回的切片缺人。

Go 里 copy 的源和目标写反成 copy(res[idx:], res[idx+1:])：这会把元素整体左移，覆盖掉 idx 处已有的人。

Java 用 res.add(person) 追加而非按下标插入：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 会原样返回排序后的数组 [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]，除 [7,0] 外几乎所有人的 k 都不对。

toArray 传入 new int[0][] 之外的错误维度，或直接强转 Object[]：res.toArray() 返回 Object[]，强转成 int[][] 抛 ClassCastException。

误以为 k 统计的是严格更高的人：[[5,0],[5,2]] 这类同身高用例下，若按「严格大于」理解，会认为两人互不计数，从而把 [5,2] 放错位置。

相似题目

题目	难度	考察点
315. 计算右侧小于当前元素的个数	困难	本题的逆问题——给顺序求计数，需要树状数组或归并排序在 $O(n \log n)$ 内统计
354. 俄罗斯套娃信封问题	困难	同样是「一维降序、另一维升序」的排序技巧，但排完后接的是最长递增子序列
452. 用最少数量的箭引爆气球	中等	按区间右端排序后贪心，正确性靠交换论证而非单向影响
435. 无重叠区间	中等	排序后贪心保留右端最小的区间，决策一旦做出就不再回头，无需插入操作
56. 合并区间	中等	按左端升序排序后线性扫描合并，排序是为了让重叠关系变成相邻关系
646. 最长数对链	中等	排序后贪心选链，与本题同属「排序服务于后续线性处理」但不需要维护插入位置
179. 最大数	中等	自定义比较器是全部难点，要证明拼接比较满足传递性，与本题「规则即正确性」相通
1122. 数组的相对排序	简单	排序键由外部数组指定，练习把业务规则翻译成比较器的基本功