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

这道题到底在问什么

输入

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]]

先想最直接的笨办法

笨办法：把所有人排成 n 的阶乘种顺序，逐个检查每个人前面的高个数是否等于 k。n 一到 2000，排列数直接爆炸，根本跑不动。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法：把所有人排成 n 的阶乘种顺序，逐个检查每个人前面的高个数是否等于 k。n 一到 2000，排列数直接爆炸，根本跑不动。
2. 4转折点：先按身高从高到低排，同身高的按 k 从小到大排。这样每次要插的人，都比队列里已有的人矮或一样高，于是直接把他插到下标 k，前面就刚好有 k 个不比他矮的人。
3. 5为什么后插的矮个不会破坏前面高个的 k？因为高个只数「不比自己矮的人」，而后插进来的矮个比他矮，根本不会被高个数进去。插矮个对高个的 k 是「隐形」的。
4. 6people.sort：身高降序，同高 k 升序排完序：7、7、6、5、5、4 身高从高到低。注意主舞台这个空队列就是答案 ans，待插入的人在右侧面板里排好队，一个个往里塞。
5. 7ans.insert(0, [7,0])最高的 7 先进场。它的 k=0，要求前面没人不比它矮，所以放到队首下标 0。
6. 8ans.insert(1, [7,1])第二个 7，k=1，插到下标 1。它前面正好站着一个 [7,0]，身高 7 不比它矮，k 满足。
7. 9ans.insert(1, [6,1])6 比队列里的两个 7 都矮。它 k=1，插到下标 1：原来站这儿的 [7,1] 被往右挤一格。看下标 2 的 [7,1] 是怎么被顶过去的。
8. 10insert 的真相：插一个，后面全体右移一格把这一步删掉文字也要看懂：[6,1] 占了下标 1，[7,1] 从 1 退到 2。[7,1] 前面新增的是更矮的 [6,1]，6 不比 7 矮的人不增加，所以 [7,1] 的 k=1 依然成立。这就是「矮个对高个隐形」的现场。
9. 11ans.insert(0, [5,0])5 比前面所有人都矮，k=0，插到队首。后面三个人全体右移一格，但他们前面新增的是更矮的 5，k 全都不受影响。
10. 12ans.insert(2, [5,2])第二个 5，k=2，插到下标 2。它前面是 [5,0] 和 [7,0]，身高都至少 5，正好 2 个，条件满足。
11. 13ans.insert(4, [4,4])最矮的 4 最后进场，k=4，插到下标 4。它前面四个人身高都不比 4 矮，全部满足，队列拼完。
12. 14验证：数 [6,1] 前面有几个不比 6 矮的人随手抽查 [6,1]。它前面三个人里，只有 [7,0] 身高不比 6 矮，另外两个 5 都比 6 矮不算。正好 1 个，k=1 成立。算法对了。
13. 15return ans最终队列不一定按身高有序，但每个人的 k 条件全都对。注意：答案可能不唯一，但本题保证至少有一个合法答案。
14. 18一句话本质：当一个约束只跟「比自己更高的人」有关，就先把高个排定，后来的矮个对高个完全隐形，于是 k 直接当插入下标。
15. 20若同高按 k 降序，错误一路潜伏到 [5,2] 才爆用本课代码真跑「同高 k 降序」：前几步并不会当场崩，错误是悄悄累积的——同高的两人里 k 大的先插，随后被 k 小的插入挤动，相对次序就乱了。最终在更矮的 [5,2] 处暴露：它前面挤进了 [5,0]、[7,0]、[6,1] 三个不矮于 5 的人，而 k 只要 2，对不上。错误队列 [[5,0],[7,0],[6,1],[5,2],[4,4],[7,1]] 中标红的 [5,2] 就是崩点。这才是「同高必须 k 升序」的真实理由。
16. 24这题的内核是「先按一个维度排定，让后续操作对它无害」。同一招还能解：LC135 分发糖果（左右各扫一遍）、LC435 无重叠区间（按右端点排序贪心）、LC452 用最少箭引爆气球。学会「排哪个维度能让后续不破坏前面」，这一类贪心就通了——更多在 贪心专题 继续，卡住时让小欧私教陪你把这套骨架套到下一题。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def reconstructQueue(self, people):
        # 身高降序；同高时 k 升序
        people.sort(key=lambda p: (-p[0], p[1]))
        ans = []
        for p in people:
            ans.insert(p[1], p)  # k 当下标插入
        return ans

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b){
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
        vector<vector<int>> ans;
        for (auto& p : people)
            ans.insert(ans.begin() + p[1], p);
        return ans;
    }
};

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> ans = new ArrayList<>();
        for (int[] p : people)
            ans.add(p[1], p);  // 在下标 k 处插入
        return ans.toArray(new int[people.length][]);
    }
}

# 贪心排序通法：定排序维度 → 顺序处理 → 维护一个结构
items.sort(key=lambda x: (____, ____))  # ① 关键：先排哪个维度
result = []                              # ② 累积答案的结构
for x in items:
    pos = ____                           # ③ 由当前元素算出落点/决策
    result.insert(pos, x)  # 本题：pos = x 的 k
return result

// 贪心排序通法骨架
sort(items.begin(), items.end(), [](auto& a, auto& b){
    return /* ① 先排哪个维度，同值时按次关键字 */;
});
vector<T> result;                  // ② 累积结构
for (auto& x : items) {
    int pos = /* ③ 由 x 算落点 */;     // 本题 pos = x[1]
    result.insert(result.begin() + pos, x);
}
return result;

// 贪心排序通法骨架
Arrays.sort(items, (a, b) -> /* ① 排序维度 */);
List<T> result = new ArrayList<>();   // ② 累积结构
for (T x : items) {
    int pos = /* ③ 由 x 算落点 */;        // 本题 pos = x[1]
    result.add(pos, x);
}
// return result -> 数组

复杂度

面试官可能追问