根据身高重建队列 图解题解

根据身高重建队列到底在问什么

每个人用一对数 [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 排成降序。

Python

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

C++

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), [](auto& a, auto& b){
        return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];  // 身高降序, 同高 k 升序
    });
    vector<vector<int>> q;
    for (auto& p : people)
        q.insert(q.begin() + p[1], p);  // 插到下标 k
    return q;
}

Java

public int[][] reconstructQueue(int[][] people) {
    // 身高降序; 同高 k 升序
    Arrays.sort(people, (a, b) ->
        a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
    List<int[]> q = new ArrayList<>();
    for (int[] p : people)
        q.add(p[1], p);   // 插到下标 k
    return q.toArray(new int[q.size()][]);
}