根据身高重建队列
# 📃 题目描述
题目链接:406. 根据身高重建队列 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
假设有打乱顺序的一群人站成一个队列,数组 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]]
# 🔔 解题思路
对于这种两个维度的情况,一定是要先确定一边,然后再处理另一边:
- 确定 h:按照身高从大大小排,确保前面人的身高都高于我,若身高一致,则 k 大的人排后面
- 处理 k:新建一个队列,根据 k 作为下标依次插入队列
举个例子:[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 排序后,[[7,1],[7,0],[6,1],[5,0],[5,2],[4,4]]
新建一个队列 queue,根据排序后的数组依次进行处理:
- 对于 [7,1] 来说,它应该插入现在队列的第 1 个位置,此时队列 [null, [7,1]]
- 对于 [7,0] 来说,他应该插入现在队列的第 0 个位置,此时队列 [[7,0], [7,1]]
- 对于 [6,1] 来说,他应该插入现在队列的第 1 个位置,此时队列 [[7,0],[6,1],[7,1]],可以看到,[6, 1] 的插入并不会对原本处在第 1 个位置的 [7,1] 有什么影响,因为身高较高的我们已经先处理了,身高较矮的无论你插入在哪里,对身高较高的都不会有任何影响
- ......
最后,queue = [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
- 局部最优:优先按照身高较高的 people 的 k 来插入队列。插入操作过后的 people 满足队列属性
- 全局最优:最后都做完插入操作,整个队列就满足题目要求的队列属性了
class Solution {
public int[][] reconstructQueue(int[][] people) {
// 按照身高从大大小排,确保前面人的身高都高于我
// 若身高一致,则 k 大的人排后面
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] != o2[0]) {
return o2[0] - o1[0];
}
else {
return o1[1] - o2[1];
}
}
});
// 根据 k 执行插入, k 即对应着插入下标
LinkedList<int[]> queue = new LinkedList<>();
for (int[] p : people) {
// public void add(int index, E element);
queue.add(p[1], p);
}
return queue.toArray(new int[people.length][2]);
}
}
# 💥 复杂度分析
- 空间复杂度:O(N)
- 时间复杂度:O(NLogN)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10