题目描述#

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

解题思路#

1. 排序预处理：
   • 按身高(h)降序排序，同身高按k值升序排序
2. 贪心插入：
   • 初始化空结果队列
   • 按排序顺序，将每人插入到其k值指定的索引位置
3. 索引特性：
   • 高个子先插入，不影响后续矮个子k值计数
   • 同身高按k升序保证顺序正确性
4. 动态调整：
   • 插入操作自动维护队列顺序
   • 后续插入不会破坏已有元素的k值条件

代码实现#

1
/**
2
 * @param {number[][]} people
3
 * @return {number[][]}
4
 */
5
var reconstructQueue = function (people) {
6
    people.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]);
7
    const queue = [];
8
    people.forEach(p => queue.splice(p[1], 0, p));
9
    return queue;
10
};

相似题目#

• 计算右侧小于当前元素的个数
• 奖励最顶尖的 K 名学生