贪心
解题思路
此题有 h 和 k 两个维度，需要一个维度一个维度去考虑；
按照 k 来从小到大排序，排完之后，会发现 k 的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来；- 按照身高 h 来排序，身高一定是从大到小排（身高相同的话则 k 小的站前面），让高个子在前面；
- 此时可以确定一个维度了，就是身高，前面的节点一定都比本节点高，那么只需要按照 k 为下标重新插入队列就可以了；
局部最优：优先按身高高的 people 的 k 来插入，插入操作过后的 people 满足队列属性；
全局最优：最后都做完插入操作，整个队列满足题目队列属性；
排序完的 people
[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2]，[4, 4]]的插入过程：
- 插入 [7, 0] 到索引为 0 的位置：
[[7, 0]]- 插入 [7, 1] 到索引为 1 的位置：
[[7, 0], [7, 1]]- 插入 [6, 1] 到索引为 1 的位置：
[[7, 0], [6, 1], [7, 1]]- 插入 [5, 0] 到索引为 0 的位置：
[[5, 0], [7, 0], [6, 1], [7, 1]]- 插入 [5, 2] 到索引为 2 的位置：
[[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]- 插入 [4, 4] 到索引为 4 的位置：
[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
复杂度
-
时间复杂度：
O(n^2)，其中 n 是数组 people 的长度，需要O(nlogn)的时间进行排序，随后需要O(n^2)的时间遍历每一个人并将他们放入队列中； -
空间复杂度：
O(n)；
代码实现
var reconstructQueue = function (people) {
let queue = [];
// 1. 按照身高 h 来排序，身高一定是从大到小排（身高相同的话则 k 小的站前面）
people.sort((a, b) => b[0] !== a[0] ? b[0] - a[0] : a[1] - b[1]);
// 2. 遍历 people 并按照 k 为下标重新插入队列
for (let i = 0; i < people.length; i++) {
queue.splice(people[i][1], 0, people[i]);
}
return queue;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 860. 柠檬水找零
上一篇
评论
