当前位置：首页 > news >正文

贪心算法专题(十)：维度权衡的艺术——「根据身高重建队列」

news 2026/5/12 16:33:43

哈喽各位，我是前端小L。

欢迎来到贪心算法专题第十篇！

想象一下，一群人排队，每个人都知道自己的身高 h，也知道排在自己前面且身高大于或等于自己的人数 k。

现在队伍被打乱了，只给你这两个数字，请你把队伍恢复原状。

示例：[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

[7,0]：身高7，前面有0个比我高的（说明我站在最前面或者前面都比我矮）。
[5,2]：身高5，前面有2个比我高的。

力扣 406. 根据身高重建队列

https://leetcode.cn/problems/queue-reconstruction-by-height/

题目分析：

输入：people数组，元素为[h, k]。
输出：重排后的数组。

核心思维：高个子看不见矮个子

如果我们先按k排序，或者乱序插入，会发现极其痛苦：因为插入一个人，可能会影响后面所有人的k值（因为你不知道插入的人是不是比后面的人高）。

贪心策略：优先处理“高个子”

为什么？

因为矮个子对高个子没有影响。

只要高个子先站好了，后面无论怎么插入矮个子，高个子前面的“大于等于自己身高的人数”都不会变（因为新插进来的比他矮，他不care）。
反之，如果先排矮个子，后面来了个高个子往前面一插，矮个子的k就废了（前面多了一个比他高的，k就要变）。

确定主导维度：

先按身高h从大到小排序。
- 如果身高相同，则按k从小到大排序（因为身高一样时，k小的肯定在前面）。
插入操作：
- 排序后，我们拿到的人是：[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
- 我们按照这个顺序，把每个人插入到队列中索引为k的位置。
- 神奇之处：因为你是最矮的（相对于已经排好的人），你插入到位置k，意味着你前面正好有k个人。而这k个人都比你高（因为他们是先排进去的）。你的k属性天然满足！同时，你插进去也不会破坏已经在队伍里那些高个子的k属性。

算法流程 (JavaScript)

排序：
- h降序 (b[0] - a[0])。
- h相同时，k升序 (a[1] - b[1])。
- 排序结果：[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
插入：创建一个空数组queue。
- 拿出[7,0]-> 插到 index 0 ->[[7,0]]
- 拿出[7,1]-> 插到 index 1 ->[[7,0], [7,1]]
- 拿出[6,1]-> 插到 index 1 ->[[7,0], [6,1], [7,1]](站在7,0后面，7,1前面)
- 拿出[5,0]-> 插到 index 0 ->[[5,0], [7,0], [6,1], [7,1]]
- ...以此类推。

代码实现

在 JS 中，数组的splice方法非常适合做“在特定位置插入元素”的操作。

JavaScript

/** * @param {number[][]} people * @return {number[][]} */ var reconstructQueue = function(people) { // 1. 排序 // 优先按身高 h (p[0]) 降序排列 // 如果身高相同，按 k (p[1]) 升序排列 people.sort((a, b) => { if (a[0] !== b[0]) { return b[0] - a[0]; // h 降序 } else { return a[1] - b[1]; // k 升序 } }); let queue = []; // 2. 遍历排序后的数组，按 k 值插入 for (let i = 0; i < people.length; i++) { // splice(插入位置, 删除数量, 插入元素) // 核心贪心逻辑：因为比我高的人都已经排好了， // 我现在的 k 是多少，我就应该站在第 k 个位置上。 // 我插进去之后，不会影响后面比我高的人的 k 值（因为我比他们矮）。 queue.splice(people[i][1], 0, people[i]); } return queue; };

深度复杂度分析

时间复杂度：$O(N^2)$。
- 排序是 $O(N \log N)$。
- 但是splice插入操作本质上是数组元素的移动，最坏情况是 $O(N)$。在循环中做 $N$ 次插入，总共是 $O(N^2)$。
- （虽然是 $O(N^2)$，但因为数据量不大，且 JS 引擎对数组操作优化较好，可以通过）。
空间复杂度：$O(N)$。
- 用于存储结果队列（如果算上输出空间）。