406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

一道经典的 贪心算法 + 排序 + 插入 问题。

✅ 解题思路：贪心 + 插入

1. 高个子先安排：因为矮的人对高的人的 k 值没有影响（矮的不算“≥”），但高的人会影响矮的人。
2. 所以我们按 身高从高到低排序；身高相同，则按 k 从小到大排（因为同身高时，k 小的应更靠前）

排序规则：

(a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]

3. 然后依次插入到结果列表的 k 位置：
   • 因为前面已插入的人都 ≥ 当前身高
   • 所以直接插在第 k 位，就能保证前面恰好有 k 个 ≥ 自己的人

💡 Java 实现

import java.util.*;

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 贪心排序：按身高降序，k 升序
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1]; // 身高相同，k 小的在前
            }
            return b[0] - a[0];     // 身高高的在前
        });

        // 使用 LinkedList 支持高效插入
        List<int[]> result = new LinkedList<>();
        for (int[] p : people) {
            result.add(p[1], p); // 插入到 k 位置
        }

        return result.toArray(new int[people.length][]);
    }
}

🧪 过程演示

输入：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

1. 排序后：

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

2. 依次插入：

   • 插 [7,0] → [[7,0]]
   • 插 [7,1] → [[7,0], [7,1]]
   • 插 [6,1] → [[7,0], [6,1], [7,1]]
   • 插 [5,0] → [[5,0], [7,0], [6,1], [7,1]]
   • 插 [5,2] → [[5,0], [7,0], [5,2], [6,1], [7,1]]
   • 插 [4,4] → [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

⏱️ 复杂度分析

• 时间复杂度：
  • 排序：O(n log n)
  • 插入：每次插入 O(n)，共 n 次 → O(n²)
  • 总计：O(n²)
• 空间复杂度：O(n)（结果列表）

虽然插入是 O(n²)，但 n ≤ 2000，完全可接受。

✅ 总结

这道题是 贪心 + 巧妙插入 的典范。