406. 根据身高重建队列

🟠   🔖  树状数组 线段树 数组 排序  🔗 力扣 LeetCode

题目

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

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

Explanation:

Person 0 has height 5 with no other people taller or the same height in front.

Person 1 has height 7 with no other people taller or the same height in front.

Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.

Person 3 has height 6 with one person taller or the same height in front, which is person 1.

Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.

Person 5 has height 7 with one person taller or the same height in front, which is person 1.

Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• It is guaranteed that the queue can be reconstructed.

题目大意

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

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

示例 1：

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

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

解释：

编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。

编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。

编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。

编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。

编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。

编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。

因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入： people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• 题目数据确保队列可以被重建

解题思路

贪心策略 + 插入排序，按照贪心思想，从高个子优先的角度入手更容易满足条件约束。

1. 排序策略：

   • 按身高降序排序，对于身高相同的人按 k 升序排序：

     people.sort((a, b) => b[0] - a[0] || a[1] - b[1]);
     

   • 这样高个子优先处理，可以直接插入而不影响后续的计算。

2. 插入重建队列：

   • 遍历排序后的 people 数组，根据每个人的 k 值将其插入到对应位置：
     • 使用 splice(k, 0, item) 来确保插入位置满足 k 条件。

复杂度分析

• 时间复杂度：O(n^2)，由于 splice() 操作可能需要线性时间。
• 空间复杂度：O(n)，用于存储结果队列。

代码

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function (people) {
	// 按身高降序，k值升序排序
	people.sort((a, b) => b[0] - a[0] || a[1] - b[1]);

	let result = [];
	for (let person of people) {
		// 插入到正确位置
		result.splice(person[1], 0, person);
	}
	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
315	计算右侧小于当前元素的个数		树状数组 线段树 数组 4+	🔴	🀄️ 🔗
2512	奖励最顶尖的 K 名学生		数组 哈希表 字符串 2+	🟠	🀄️ 🔗