：维度权衡的艺术——「根据身高重建队列」)
哈喽各位，我是前端小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)$。
用于存储结果队列（如果算上输出空间）。
总结：维度的优先级
这道题是解决多维度冲突问题的教科书级案例。
当我们在两个维度（身高、k值）之间摇摆不定时，试着先固定一个维度（身高），看看是否能消除另一个维度的不确定性。
确定了由高到低排，
k就变成了纯粹的“绝对索引”。
下一题预告：用最少数量的箭引爆气球
接下来，我们将进入贪心算法中最实用、最成体系的**“区间问题”**板块（共 4 题）。
给你一堆气球，每个气球覆盖一个水平区间
[start, end]。你可以垂直射箭。
问最少射几箭能把所有气球都打破？
这道题将教会我们如何处理重叠区间。一旦掌握了这道题，后面的“无重叠区间”、“合并区间”全都是秒杀。
准备好你的弓箭了吗？下期见！
