406. 根据身高重建队列（Queue Reconstruction by Height）

频次 ★★★ · 难度 🟡 · 高频：阿里

题目

[h, k] 表示身高 h 和前面身高 ≥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]]

思路

贪心插入：先按身高降序（同身高 k 升序）排序。然后按 k 插入到结果队列的对应位置——因为高个子先排好，矮个子插队不影响高个子的 k 值。

代码

public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (a, b) ->
        a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);  // 身高降序，k 升序
    List<int[]> res = new LinkedList<>();
    for (int[] p : people) {
        res.add(p[1], p);                              // 按 k 插入
    }
    return res.toArray(new int[0][]);
}

复杂度

• 时间：O(n²) —— LinkedList 插入 O(n)，n 次
• 空间：O(n)

边界条件

• 空数组：返回空
• 单元素：直接返回

变式

• 稳定排序版：身高等同时 k 小的先插入（已实现）

易错点

• 排序规则：身高降序（先排高的），k 升序（同身高 k 小的先插入）
• 插入到 res.add(p[1], p) 的位置——k 的含义是”前面 ≥ 身高的人数”，插入到第 k 位刚好满足

面试追问

• 为什么矮个子插队不影响高个子的 k？ 因为高个子的 k 只统计”身高 ≥ 自己”的人，矮个子插到前面不影响他们的计数

关联题

• 同套路：763. 划分字母区间 —— 贪心排序
• 进阶：621. 任务调度器 —— 贪心 + 数学推导
• 知识点：“高个子先排，矮个子插队”贪心模式见贪心