406. 根据身高重建队列

406. 根据身高重建队列

题目描述

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。

每个 people[i] = [hi, ki] 表示第 i 个人的：

  • hi：身高
  • ki：在这个人前面，身高 大于等于 hi 的人数

请你重新构造并返回输入数组 people 所表示的队列。

返回的队列应该格式化为数组 queue，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性。

示例 1

text
输入：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]]

示例 2

text
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

约束

  • 1 <= people.length <= 2000
  • 0 <= hi <= 10^6
  • 0 <= ki < people.length
  • 题目数据保证队列可以被重建

核心思路

这题最开始看会有点绕，因为它不是让你简单排序，而是要满足一个条件：

  • 每个人前面恰好有 k 个身高大于等于自己的人

关键在于：

如果我们先处理高个子，再处理矮个子，矮个子就不会影响高个子的 k 统计。

这就是本题最核心的突破口。

这题至少有两种常见做法：

  • 解法一：排序 + 按下标插入（推荐）
  • 解法二：排序 + 树状数组找第 k 个空位

解法一：排序 + 按下标插入

这是这题最经典、最推荐掌握的做法。

思路拆解

我们先看一个人 [h, k] 的含义：

  • 在他前面，必须有 k 个身高 >= h 的人

如果我们先把所有高个子放好，那么后面再插入矮个子时：

  • 矮个子不会影响“前面有多少个比高个子高或一样高的人”

所以正确策略是：

  1. 按身高 从高到低 排序
  2. 如果身高相同，按 k 从小到大 排序
  3. 然后按顺序把每个人插入到结果数组的第 k 个位置

为什么插到第 k 个位置就对了？

因为当前已经放进去的人，全部都比他高，或者和他一样高。

所以：

  • 当他插入到下标 k 时
  • 他前面就正好有 k 个人满足“身高 >= 自己”

为什么相同身高要按 k 从小到大？

比如有两个人：

text
[7, 0], [7, 1]

如果先放 [7,1]，再放 [7,0]，前面的结构会被打乱。

而按 k 从小到大：

  • 先放 [7,0]
  • 再放 [7,1]

这样插入位置才是稳定正确的。

所以排序规则必须是：

ts
身高降序，k 升序

一步一步写出算法

第一步：先排序

ts
people.sort((a, b) => {
    if (a[0] !== b[0]) {
        return b[0] - a[0]
    }
    return a[1] - b[1]
})

排序后：

  • 高的在前
  • 一样高的，k 小的在前

第二步：准备结果数组

ts
const queue: number[][] = []

第三步：按 k 位置插入

ts
for (const person of people) {
    queue.splice(person[1], 0, person)
}

这里的意思是：

  • 把当前这个人插入到下标 k 的位置

因为前面已经插入的人都比他高或一样高，所以这样正好满足题意。

第四步：返回结果

ts
return queue

代码实现（TypeScript）

ts
function reconstructQueue(people: number[][]): number[][] {
    people.sort((a, b) => {
        if (a[0] !== b[0]) {
            return b[0] - a[0]
        }
        return a[1] - b[1]
    })

    const queue: number[][] = []
    for (const person of people) {
        queue.splice(person[1], 0, person)
    }

    return queue
}

复杂度分析

  • 排序复杂度：O(n log n)
  • 每次数组插入最坏：O(n)
  • 总时间复杂度：O(n^2)
  • 空间复杂度：O(n)

这题 n <= 2000，所以这个做法完全够用。

这一解法的优缺点

优点：

  • 思路非常巧妙
  • 代码短
  • 是这题标准解法

缺点：

  • 如果第一次看到，很难直接想到“先排高个子”
  • splice 插入本质上还是 O(n)

解法二：排序 + 树状数组找空位

这个做法更偏进阶，适合你想进一步理解“按条件把人放进空位”的过程。

思路拆解

除了“先排高个子再插入”外，我们还可以反过来想：

  • 如果先处理矮个子
  • 那么一个人 [h, k] 需要放到一个位置
  • 这个位置的前面必须恰好保留 k 个将来给“身高 >= h”的人占据的位置

这个思路写起来会更复杂，一种常见实现是：

  1. 按身高 从低到高 排序
  2. 如果身高相同，按 k 从高到低 排序
  3. 用树状数组维护哪些位置还是空的
  4. 对于当前这个人，找到“第 k + 1 个空位”把他放进去

为什么是第 k + 1 个空位？

因为：

  • 这些空位将来会留给比他高或和他一样高的人
  • 他前面需要恰好有 k 个这样的人
  • 所以他应该占据第 k + 1 个可用位置

这是一个更抽象但也更高级的做法。

为什么排序要“身高升序，k 降序”？

因为如果同样身高的人里先放 k 小的，会影响后面 k 大的可用空位分布。

按：

  • 身高升序
  • k 降序

可以保证同身高的人在放位置时不会相互破坏条件。

一步一步写出算法

第一步：先排序

ts
people.sort((a, b) => {
    if (a[0] !== b[0]) {
        return a[0] - b[0]
    }
    return b[1] - a[1]
})

第二步：初始化树状数组

树状数组维护每个位置是否空着：

  • 初始时每个位置都是空位，值为 1
  • 放入一个人后，这个位置变成 0

第三步：为每个人找到第 k + 1 个空位

树状数组支持：

  • 求前缀和
  • 二分 / 二进制跳跃查找第一个前缀和达到目标的位置

这样就能快速找到第 k + 1 个空位。

第四步：把人放进去并更新树状数组

ts
result[position] = person
bit.add(position + 1, -1)

因为该位置不再是空位了。

代码实现（TypeScript）

ts
class FenwickTree {
    private tree: number[]

    constructor(size: number) {
        this.tree = new Array(size + 1).fill(0)
    }

    add(index: number, delta: number): void {
        while (index < this.tree.length) {
            this.tree[index] += delta
            index += index & -index
        }
    }

    query(index: number): number {
        let sum = 0
        while (index > 0) {
            sum += this.tree[index]
            index -= index & -index
        }
        return sum
    }

    findKth(target: number): number {
        let index = 0
        let bitMask = 1

        while ((bitMask << 1) < this.tree.length) {
            bitMask <<= 1
        }

        while (bitMask > 0) {
            const next = index + bitMask
            if (next < this.tree.length && this.tree[next] < target) {
                index = next
                target -= this.tree[next]
            }
            bitMask >>= 1
        }

        return index + 1
    }
}

function reconstructQueue(people: number[][]): number[][] {
    const n = people.length

    people.sort((a, b) => {
        if (a[0] !== b[0]) {
            return a[0] - b[0]
        }
        return b[1] - a[1]
    })

    const bit = new FenwickTree(n)
    for (let i = 1; i <= n; i++) {
        bit.add(i, 1)
    }

    const result = new Array<number[]>(n)

    for (const person of people) {
        const position = bit.findKth(person[1] + 1) - 1
        result[position] = person
        bit.add(position + 1, -1)
    }

    return result
}

复杂度分析

  • 排序复杂度：O(n log n)
  • 每个人查找空位和更新：O(log n)
  • 总时间复杂度：O(n log n)
  • 空间复杂度：O(n)

这个做法复杂一些，但复杂度比 splice 更优。

这一解法的优缺点

优点：

  • 时间复杂度更优
  • 能锻炼“树状数组 + 第 k 个位置”这类技巧

缺点：

  • 很不直观
  • 不如第一种方法好记、好写

两种解法对比

解法时间复杂度空间复杂度特点
排序 + 按下标插入O(n^2)O(n)最经典，最推荐
排序 + 树状数组找空位O(n log n)O(n)更进阶，复杂度更优

如果你是第一次做这题，建议一定先彻底理解第一种做法。

手动模拟一遍经典解法

以：

text
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

为例。

第一步：排序

按“身高降序，k 升序”排序后：

text
[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

第二步：依次插入

先插入 [7,0]：

text
[7,0](<7,0.md>)

再插入 [7,1]，放到下标 1：

text
[[7,0],[7,1]]

再插入 [6,1]，放到下标 1：

text
[[7,0],[6,1],[7,1]]

再插入 [5,0]，放到下标 0：

text
[[5,0],[7,0],[6,1],[7,1]]

再插入 [5,2]，放到下标 2：

text
[[5,0],[7,0],[5,2],[6,1],[7,1]]

最后插入 [4,4]，放到下标 4：

text
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

这就是答案。

面试时最容易错的点

1. 排序规则不要写反

经典解法的排序规则是：

text
身高降序，k 升序

不是：

  • 身高升序
  • 或者 k 降序

这个顺序一旦错了，后面的插入就不成立。

2. k 不是“前面有多少个人”

k 的意思是：

  • 前面有多少个 身高大于等于自己 的人

不是单纯前面的人数。

3. 为什么插到下标 k 就行

因为在经典解法里，当前已经放进去的人：

  • 全都比当前人高
  • 或者和当前人一样高但 k 更小

所以插到下标 k 后，前面的这些人全部都算数。

4. 树状数组做法更难，不是首选

面试里如果时间有限：

  • 优先写第一种
  • 第二种作为进阶补充思路即可

一句话总结

这题的本质是：

先把高个子的位置确定下来，再让矮个子插进去，因为矮个子不会影响高个子的计数条件。

  • 想写最经典答案：用 排序 + 按下标插入
  • 想进一步优化复杂度：用 树状数组找空位

推荐你最后记住的标准写法

如果你准备刷题，建议优先记下面这个版本：

ts
function reconstructQueue(people: number[][]): number[][] {
    people.sort((a, b) => {
        if (a[0] !== b[0]) {
            return b[0] - a[0]
        }
        return a[1] - b[1]
    })

    const queue: number[][] = []
    for (const person of people) {
        queue.splice(person[1], 0, person)
    }

    return queue
}

因为这个版本：

  • 思路最巧妙
  • 代码最短
  • 是这题公认的标准解法