【刷穿 LeetCode】502. IPO : 详解优先队列实现贪心算法

简介: 【刷穿 LeetCode】502. IPO : 详解优先队列实现贪心算法

网络异常,图片无法展示
|

题目描述



这是 LeetCode 上的 502. IPO ,难度为 困难


Tag : 「贪心」、「优先队列」、「堆」


假设 力扣(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 <= 10^5105
  • 0 <= w <= 10^9109
  • n == profits.length
  • n == capital.length
  • 1 <= n <= 10^5105
  • 0 <= profits[i] <= 10^4104
  • 0 <= capital[i] <= 10^9109


贪心 + 优先队列(堆)



由于每完成一个任务都会使得总资金 w 增加或不变。因此对于所选的第 ii 个任务而言,应该在所有「未被选择」且启动资金不超过 w 的所有任务里面选利润最大的。


可通过「归纳法」证明每次都在所有候选中选择利润最大的任务,可使得总资金最大。


对于第 ii 次选择而言(当前所有的资金为 ww),如果选择的任务利润为 curcur,而实际可选的最大任务利润为 maxmaxcur <= maxcur<=max )。


将「选择 curcur」调整为「选择 maxmax」,结果不会变差:


  1. 根据传递性,由 cur <= maxcur<=max 可得 w + cur <= w + maxw+cur<=w+max,可推导出调整后的总资金不会变少;
  2. 利用推论 11,由于总资金相比调整前没有变少,因此后面可选择的任务集合也不会变少。这意味着 至少可以维持ii 次选择之后的所有原有选择。


至此,我们证明了将每次的选择调整为选择最大利润的任务,结果不会变差。


当知道了「每次都应该在所有可选择的任务里选利润最大」的推论之后,再看看算法的具体流程。


由于每完成一个任务总资金都会 增大/不变,因此所能覆盖的任务集合数量也随之 增加/不变 。


因此算法核心为「每次决策前,将启动资金不超过当前总资金的任务加入集合,再在里面取利润最大的任务」。


「取最大」的过程可以使用优先队列(根据利润排序的大根堆),而「将启动资金不超过当前总资金的任务加入集合」的操作,可以利用总资金在整个处理过程递增,而先对所有任务进行预处理排序来实现。


具体的,我们可以按照如下流程求解:


  1. 根据 profitscapital 预处理出总的任务集合二元组,并根据「启动资金」进行升序排序;
  2. 每次决策前,将所有的启动资金不超过 ww 的任务加入优先队列(根据利润排序的大根堆),然后从优先队列(根据利润排序的大根堆),将利润累加到 ww
  3. 循环步骤 22,直到达到 kk 个任务,或者队列为空(当前资金不足以选任何任务)。


代码:


class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new int[]{capital[i], profits[i]});
        }
        Collections.sort(list, (a,b)->a[0]-b[0]);
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int i = 0;
        while (k-- > 0) {
            while (i < n && list.get(i)[0] <= w) q.add(list.get(i++)[1]);
            if (q.isEmpty()) break;
            w += q.poll();
        }
        return w;
    }
}
复制代码


  • 时间复杂度:构造出二元组数组并排序的复杂度为 O(n\log{n})O(nlogn);大根堆最多有 nn 个元素,使用大根堆计算答案的复杂度为 O(k\log{n})O(klogn)。整体复杂度为 O(\max(n\log{n}, k\log{n}))O(max(nlogn,klogn))
  • 空间复杂度:O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.502 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
4天前
|
存储 算法 JavaScript
怎么刷算法,leetcode上有哪些经典题目
怎么刷算法,leetcode上有哪些经典题目
18 0
|
4天前
|
算法 Java
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
27 1
|
4天前
|
算法 Java
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
25 0
|
4天前
|
算法 Java
[Java·算法·简单] LeetCode 392. 判断子序列 详细解读
[Java·算法·简单] LeetCode 392. 判断子序列 详细解读
42 0
|
4天前
|
存储 canal 算法
[Java·算法·简单] LeetCode 125. 验证回文串 详细解读
[Java·算法·简单] LeetCode 125. 验证回文串 详细解读
30 0
|
4天前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
22 0
|
4天前
|
算法
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
23 3
|
4天前
|
存储 算法
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
22 1
|
4天前
|
算法
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
18 3
|
4天前
|
算法
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
34 1