LeetCode 406. 根据身高重建队列

约 4 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 2-5 腾讯 华为
标签
数组 排序 线段树 树状数组

题目描述

✅ 406. 根据身高重建队列

image-20260928224425820

image-20260928224425821

题意分析

每个人用 [h, k] 表示：身高为 h，最终队列中排在他前面、且身高不低于 h 的人数恰好为 k。根据打乱的这些记录，恢复一条满足所有人条件的队列。

k 不是最终下标，也不统计前面的矮个子；与自己同高的人要计入。题目保证能够重建，输出保留每个人的完整记录，只调整排列顺序。

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

核心思路

[!blue]

难点是一个人的有效前驱取决于身高。先按身高从高到低处理，就能让当前已放入列表的人全部不矮于新人，列表中的每个人都计入新人的 k，于是它可以直接作为插入下标。

把新人插到下标 k，其前面正好有 k 个已有元素，因此他的条件立即满足。这里是插入而非覆盖，原来从该位置开始的人需要整体向后移动，所有记录仍各保留一份。

还要保证后续操作不会破坏已经放好的人。之后加入的严格矮者，即使插到高者前面，也不计入高者的有效前驱，所以无影响；同身高的人则必须按 k 从小到大处理，较大 k 的后来者插在已放同高者之后，不会增加他们前面的同高人数。

两条排序规则因此缺一不可：身高降序使已有列表中的所有人都能为当前人计数，同高 k 升序使后来的同高者不会破坏已经满足的约束。有解的前提也保证每次所需的插入下标都在当前列表允许范围内。

Java 用列表按下标插入；Go 先把切片长度加一，再用支持重叠区间的 copy 将后缀右移，最后写入空出的下标。实现会排序输入数组，然后构造结果队列。

解题步骤

  1. 将记录按身高降序排序，同身高按 k 升序排序。
  2. 从空结果列表开始，依次读取排序后的人。
  3. 在结果下标 person[1] 处插入当前记录，原后缀整体右移。
  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]);
    }
}

import "sort"

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)$，按下标插入的移位主导。
  • 空间复杂度：$O(n)$，结果与排序辅助空间。

关键点总结

[!green]

  • 原始的 k 不是最终下标，只有按身高顺序构造的当前列表里，才等价于插入下标。
  • 严格矮者不影响高者，同高者会相互计数，需要额外按 k 升序控制。
  • 插入保留所有已有元素，不能用覆盖赋值代替。
  • Go 必须先扩长再右移，copy 能正确处理重叠源区间与目标区间。

易错点总结

[!yellow]

  • 同身高按 k 降序处理，可能过早使用当前列表尚不存在的插入位置，也会破坏同高约束。
  • 按身高升序后仍直接以 k 插入，已有矮者不能全部计入有效前驱。
  • 直接覆盖结果下标会丢掉原来的人员记录，应执行真正的插入。
  • person[0] 是身高，person[1] 才是所需人数，不能混作插入位置。

相似题目

题目 难度 关联与区别
1389. 按既定顺序创建目标数组 简单 同样根据插入位置构造序列，本题先按身高降序，使k恰好成为当前队列的插入下标。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/74178578
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！