LeetCode IPO问题题解

LeetCode IPO问题题解题目描述给定初始资本 w最多完成 k 个项目。每个项目有利润和最低资本要求。找到能够获得的最大资本。示例输入capital [0,1,2,3],profits [1,2,3,5],k 2,w 0输出4解题思路方法堆思路使用两个堆一个最大堆和一个最小堆。最小堆按最低资本要求排序最大堆按利润排序。从最小堆中选择所有资本要求小于等于 w 的项目将其利润加入最大堆。从最大堆中选择利润最大的项目更新资本 w。重复 k 次。复杂度分析时间复杂度O(k log n)空间复杂度O(n)代码实现import heapq def find_maximum_capital(capital, profits, k, w): n len(profits) projects sorted(zip(capital, profits)) max_heap [] result w j 0 for _ in range(k): while j n and projects[j][0] result: heapq.heappush(max_heap, -projects[j][1]) j 1 if not max_heap: break result -heapq.heappop(max_heap) return result # 测试 def test_find_maximum_capital(): capital [0, 1, 2, 3] profits [1, 2, 3, 5] k, w 2, 0 print(find_maximum_capital(capital, profits, k, w)) # 输出4 if __name__ __main__: test_find_maximum_capital()总结IPO问题是堆的典型应用通过两个堆来选择能够完成的项目。