优先级队列
解题思路
如果不限制次数下可以获取的最大利润，该如何处理？只需将所有的项目按照资本的大小进行排序，依次购入项目 i ，同时手中持有的资本增加 profits[i] ，直到手中的持有的资本无法启动当前的项目为止；
如果初始资本
w≥max(capital)，直接返回利润中的 k 个最大元素的和即可；当前可以选择的次数最多为 k 次，这就意味着应该贪心地保证选择每次投资的项目获取的利润最大，这样就能保持选择 k 次后获取的利润最大；
首先将项目按照所需资本的从小到大进行排序，每次进行选择时，假设当前手中持有的资本为 w ，应该从所有投入资本小于等于 w 的项目中选择利润最大的项目 j ，然后此时更新手中持有的资本为
w+profits[j]，同时再从所有花费资本小于等于w+profits[j]的项目中选择，按照上述规则不断选择 k 次即可；利用大根堆的特性，将所有能够投资的项目的利润全部压入到堆中，每次从堆中取出最大值，然后更新手中持有的资本，同时将待选的项目利润进入堆，不断重复上述操作；
如果当前的堆为空，则此时应当直接返回；
复杂度
-
时间复杂度：
O((n+k)logn)，其中 n 是数组 profits 和 capital 的长度，k 表示最多的选择数目；- 需要
O(nlogn)的时间复杂度来来创建和排序项目，往堆中添加元素的时间不超过O(nlogn)； - 每次从堆中取出最大值并更新资本的时间为
O(klogn)；
- 需要
-
空间复杂度：
O(n)，其中 n 是数组 profits 和 capital 的长度，空间复杂度主要取决于创建用于排序的数组和大根堆；
代码实现
var findMaximizedCapital = function (k, w, profits, capital) {
// 1. 将成本和利润放到同一个二维数组里面，方便操作
let arr = capital.map((c, i) => [c, profits[i]]);
// 2. 按照成本升序排序，成本覆盖才能去做这个项目
arr.sort((a, b) => a[0] - b[0]);
// 3. 创建大顶堆，里面放入所有能做的项目，出队的第一个就是最大利润的项目
let heap = new Heap((a, b) => a > b);
let cur = 0;
// 4. 最多能做 k 个项目
while (k > 0) {
// 4-1. 满足手里资金 >= 成本的情况下，利润全部放到大顶堆里面
while (cur < arr.length && arr[cur][0] <= w) {
heap.push(arr[cur][1]);
cur++;
}
// 4-2. 选择最大的利润
if (heap.size > 0) {
w += heap.pop();
} else {
break;
}
k--;
}
return w;
};
class Heap {
constructor(compare) {
this.arr = [0]; // 忽略 0 这个索引,方便计算左右节点
this.compare = compare ? compare : (a, b) => a > b; // 默认是大顶堆
}
get size() {
return this.arr.length - 1;
}
// 新增元素
push(item) {
this.arr.push(item);
this.shiftUp(this.arr.length - 1);
}
// 元素上浮，k 是索引
shiftUp(k) {
let { arr, compare, parent } = this;
// 当前元素 > 父元素，则进行交换
while (k > 1 && compare(arr[k], arr[parent(k)])) {
this.swap(parent(k), k);
k = parent(k); // 更新 k 的位置为父元素的位置（交换了位置）
}
}
// 弹出堆顶
pop() {
if (this.arr.length == 1) return null;
this.swap(1, this.arr.length - 1);// 将结尾元素和堆顶元素交换位置
let head = this.arr.pop(); // 删除堆顶
this.sinkDown(1); // 再做下沉操作
return head;
}
// 元素下沉
sinkDown(k) {
let { arr, compare, left, right, size } = this;
while (left(k) <= size) {
// 1. 拿到左右节点的最大值
let child = left(k);
if (right(k) <= size && compare(arr[right(k)], arr[child])) {
child = right(k);
}
// 2. k 满足大顶堆或小顶堆，什么都不做
if (compare(arr[k], arr[child])) {
return;
}
// 3. 交换位置后，继续下沉操作
this.swap(k, child);
k = child; // 更新位置
}
}
// 获取堆顶元素
peek() {
return this.arr[1];
}
// 获取左边元素节点
left(k) {
return k * 2;
}
// 获取右边元素节点
right(k) {
return k * 2 + 1;
}
// 获取父节点
parent(k) {
return Math.floor(k >> 1);
}
// i、j 交换位置
swap(i, j) {
[this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]];
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 460. LFU 缓存
上一篇
评论
