题目
假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
答案保证在 32 位有符号整数范围内。
示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6
提示：
- 1 <= k <= 105
- 0 <= w <= 109
- n == profits.length
- n == capital.length
- 1 <= n <= 105
- 0 <= profits[i] <= 104
- 0 <= capital[i] <= 109
题解
/*
* 时间: 2021-09-08 13:00
* 分析: 求最大利润
* 1. 项目数 k
* 2. 初始资本 w
* 3. 纯利润 profits
* 4. 启动资本 capital
* 思路:
* 1. 贪心算法
* a. 使用HashMap存储利润和启动资本
* b. 按利润和启动资本进行排序
* c. 优先选取启动资本允许的最大利润项目
* 优化:
* 1. 在 思路1 的基础上优化: 找到局部最优解后退出当前循环
* 2. 在 优化1 的基础上优化: 将ArrayList替换为LinkedList, 解决超时问题
* 参考:
* 1. 使用优先队列解题 (当前实现)
*/
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int len = profits.length;
int[][] array = new int[len][2];
for (int i = 0; i < len; i++) {
array[i][0] = capital[i];
array[i][1] = profits[i];
}
// 按启动资本升序排列
Arrays.sort(array, ((o1, o2) -> o1[0] - o2[0]));
int cur = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(((o1, o2) -> o2 - o1));
for (int i = 0; i < k; i++) {
// 将满足最低启动资本要求的项目压入优先队列, 且按受益降序排列
for (; cur < len && array[cur][0] <= w; cur++) {
pq.add(array[cur][1]);
}
// 获取最大受益的项目并计入总收益
if (pq.isEmpty()) {
break;
}
w += pq.poll();
}
return w;
}
}
Q.E.D.