Leetcode 每日一题 ------ 502. IPO
-
从Leetcode 每日一题练习继续讨论：
502. IPO
502. IPO
题解
本题是一道难题, 思路总体还是比较清晰的, 本题目标是取k个不同的project, 使得最后能得到的利润最大. 每一个project都有对应的利润和成本. 要使最后的整体利润最大, 无疑只要在当前可以选择(即成本在当前已获得的资金范围内)的所有project中选择利润最大的, 再更新可选择的project, 再次选择利润最大的. 如此反复直到选择完全部的k个project即可. 有了这个思路, 我们要解决两个问题. 1. 如何高效的选择利润最大的project, 最大堆显然是一个不错的选择. 2. 如何更新可选择的project的范围, 我们将project的成本排序, 每次获得了更多的本金后就将小于当前本金的所有project的利润加入最大堆, 为了每次只放入新增加的project, 可以对pro...
阅读原文
