502。首次公开募股
难
假设LeetCode即将开始IPO。为了能以好价格出售股份给风险投资公司，LeetCode 希望在IPO之前开展一些增资项目。由于资源有限，它只能在IPO之前完成最多k个不同的项目。帮助 LeetCode 设计在完成最多 k 个不同项目后最大化其总资本的最佳方式。
给你n个项目，其中第i项目有纯利润利润[i]，并且需要最低资本资本[i]来启动它。
最初，你有w资本。当您完成一个项目时，您将获得其纯利润，该利润将添加到您的总资本中。
从给定项目中选择至多 k 个不同项目的列表，以最大化您的最终资本，并返回最终最大化的资本。
答案保证适合 32 位有符号整数。
示例1：
- 输入： k = 2，w = 0，利润 = [1,2,3]，资本 = [0,1,1]
- 输出： 4
- 说明： 由于您的初始资金为0，因此您只能启动索引为0的项目。
完成后你将获得利润1，你的资本变成1.
使用大写1，您可以启动索引为1的项目或索引为2的项目。
由于您最多可以选择2个项目，因此您需要完成索引为2的项目才能获得最大资本。
因此，输出最终最大化的资本，即0 + 1 + 3 = 4。
示例2：
- 输入： k = 3，w = 0，利润 = [1,2,3]，资本 = [0,1,2]
- 输出： 6
限制：
- 1 5
- 0 9
- n == 利润.长度
- n == 大写.长度
- 1 5
- 0 4
- 0 9
解决方案：
类解决方案{
/*** @param 整数 $k
* @param 整数 $w
* @param Integer[] $利润
* @param Integer[] $资本
* @return 整数*/
函数 findMaximizedCapital($k, $w, $profits, $capital) {
$n = 计数($资本);
$minCapitalHeap = new SplMinHeap();
为 ($i = 0; $i < $n; ++$i) {
$minCapitalHeap->insert([$capital[$i], $profits[$i]]);
}
$maxProfitHeap = new SplMaxHeap();
而（$k-->0）{
while (!$minCapitalHeap->isEmpty() && $minCapitalHeap->top()[0] <= $w) {
$maxProfitHeap->insert($minCapitalHeap->extract()[1]);
}
if ($maxProfitHeap->isEmpty()) {
休息;
}
$w += $maxProfitHeap->extract();
}
返回$w；
}
}
联系链接
- 领英
- GitHub
