vvrf / DSA.log

问题拆解

每个人由 [h, k] 描述：身高 h，且排在他前面、身高不低于他的人恰好有 k 个。给出打乱的数组，重建队列。

难点在于两个维度互相牵制：一个人的 k 是否满足，取决于其他人站在哪，随便放一个人都可能牵一发动全身。破局的观察是身高的不对称性：矮个子在高个子眼里是“透明”的——身高更矮的人无论插在哪，都不会计入前面任何一个更高的人的 k。所以按身高从高到低安排，先就位的人永远不受后来者影响。

让约束单向化：先放高个，此时每个矮个的 k 恰好数的是“已就位的人里排在我前面的个数”，插到下标 k 处就是他的最终位置。

身高降序排序 + 按 k 插入

排序规则：身高降序；身高相同时 k 升序——同身高的人互相计入对方的 k，k 小的必须先放（若 k 大的先放，后来者插到它前面时会破坏它的计数）。然后依次把每个人插入列表的下标 k 处即可。

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[]> queue = new ArrayList<>();
    for (int[] p : people) {
        queue.add(p[1], p); // k 就是他在当前队列里的下标
    }
    return queue.toArray(new int[queue.size()][]);
}

def reconstructQueue(people: List[List[int]]) -> List[List[int]]:
    # 身高降序；同身高按 k 升序
    people.sort(key=lambda p: (-p[0], p[1]))
    queue = []
    for p in people:
        queue.insert(p[1], p)  # k 就是他在当前队列里的下标
    return queue

func reconstructQueue(people [][]int) [][]int {
    // 身高降序；同身高按 k 升序
    slices.SortFunc(people, func(a, b []int) int {
        if a[0] != b[0] {
            return b[0] - a[0]
        }
        return a[1] - b[1]
    })
    queue := make([][]int, 0, len(people))
    for _, p := range people {
        queue = slices.Insert(queue, p[1], p) // k 就是他在当前队列里的下标
    }
    return queue
}

pub fn reconstruct_queue(people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let mut people = people;
    // 身高降序；同身高按 k 升序
    people.sort_by(|a, b| b[0].cmp(&a[0]).then(a[1].cmp(&b[1])));
    let mut queue: Vec<Vec<i32>> = Vec::with_capacity(people.len());
    for p in people {
        let k = p[1] as usize;
        queue.insert(k, p); // k 就是他在当前队列里的下标
    }
    queue
}

为什么插入到下标 k 就对了？处理到某个人时，列表里的人身高全都不低于他，所以“排在他前面且不矮于他的人数”就等于他的下标——插到 k 处，他自己的约束立刻满足。而对已就位的人来说，新来的比他们矮（或同高但 k 更大、插在更后面），无论插到哪都不增加他们的计数，已满足的约束不会被破坏。归纳下去，全部插完时人人满足。最容易错的是同身高的次序：160 和 160 互相“看得见”，如果按 k 降序处理，先放的 [160, 1] 会被后插到下标 0 的 [160, 0] 顶到前面多算一个人。

复杂度

指标	复杂度	原因
时间	`O(n²)`	排序 O(n log n)，但每次向列表中部插入是 O(n)
空间	`O(n)`	结果列表（不计排序的栈空间）

可以迁移的模式

双维度约束先按一个维度排序，把它变成“已定序”的背景，另一个维度就退化为单点决策；
“后来者不影响先就位者”是插入型贪心的正确性来源，排序方向要朝着让影响单向流动的方向选；
主关键字降序时，次关键字的方向要单独推理（这里 k 升序），想当然同向是常见错因。

同类套路还有用最少的箭引爆气球、无重叠区间：先排序消掉一个维度，剩下的贪心往往一步到位。