Appearance
实战：IPO 问题
选择项目以最大化利润，需要在资本限制下做出最优决策。这是一道贪心 + 双堆的经典问题。
问题描述
LeetCode 502. IPO
假设你是一位风险投资家，最初有 w 资本。你想在 IPO 之前通过做项目来增加资本。
每个项目 i 有：
profits[i]：完成后获得的纯利润capital[i]：启动所需的最低资本
你最多可以做 k 个项目，每个项目只能做一次。完成项目后，利润会加入你的资本。
返回最终能获得的最大资本。
示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
- 初始资本 0，可以做项目 0（资本要求 0）
- 完成后获利 1，资本变为 1
- 现在可以做项目 1 或 2（都要求资本 1）
- 选择利润更高的项目 2，获利 3
- 最终资本 = 0 + 1 + 3 = 4示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6
解释：按顺序做三个项目，0 → 1 → 4 → 6约束条件：
1 <= k <= 10^50 <= w <= 10^91 <= n <= 10^50 <= profits[i] <= 10^40 <= capital[i] <= 10^9
问题分析
贪心策略
每一步应该如何选择？
直觉：在能做的项目中，选利润最高的。
为什么这是最优的？
假设当前资本是 w，有两个可做的项目：
- 项目 A：利润 10
- 项目 B：利润 5
先做 A 后资本变为 w+10，再做 B 后变为 w+15。 先做 B 后资本变为 w+5，再做 A 后变为 w+15。
结果相同！但如果 k 有限制，或者某些项目在做完 A 之后才能解锁，先做利润高的更有可能最大化总收益。
数据结构设计
需要高效地解决两个问题：
- 随着资本增加，快速找出新解锁的项目
- 在所有可做的项目中，快速找利润最高的
解决方案：用两个堆
| 堆 | 类型 | 排序依据 | 作用 |
|---|---|---|---|
| capitalHeap | 最小堆 | 资本要求 | 快速找出新解锁的项目 |
| profitHeap | 最大堆 | 利润 | 快速找出利润最高的项目 |
解法
javascript
function findMaximizedCapital(k, w, profits, capital) {
const n = profits.length;
// 按资本要求排序的最小堆
// 存储 [资本要求, 利润]
const capitalHeap = new MinHeap((a, b) => a[0] - b[0]);
// 把所有项目加入资本堆
for (let i = 0; i < n; i++) {
capitalHeap.insert([capital[i], profits[i]]);
}
// 按利润排序的最大堆
const profitHeap = new MaxHeap((a, b) => a - b);
for (let i = 0; i < k; i++) {
// 把所有当前资本能做的项目移到利润堆
while (capitalHeap.size() > 0 && capitalHeap.peek()[0] <= w) {
const [cap, profit] = capitalHeap.extract();
profitHeap.insert(profit);
}
// 如果没有能做的项目，提前结束
if (profitHeap.size() === 0) {
break;
}
// 选利润最高的项目
w += profitHeap.extract();
}
return w;
}执行过程详解
k=2, w=0, profits=[1,2,3], capital=[0,1,1]
初始化：
capitalHeap: [(0,1), (1,2), (1,3)] // 按资本排序
profitHeap: []
w = 0
【第 1 轮】
1. 移动可做的项目（capital ≤ 0）
移动 (0,1)
capitalHeap: [(1,2), (1,3)]
profitHeap: [1]
2. 选利润最高的：1
w = 0 + 1 = 1
【第 2 轮】
1. 移动可做的项目（capital ≤ 1）
移动 (1,2), (1,3)
capitalHeap: []
profitHeap: [3, 2] // 最大堆顶是 3
2. 选利润最高的：3
w = 1 + 3 = 4
结果：4可视化：
资本堆 利润堆 当前资本
(按资本排序) (按利润排序)
初始 [(0,1),(1,2),(1,3)] [] w=0
轮1: [(1,2),(1,3)] [1]
选择: ↓ w=0+1=1
轮2: [] [3,2]
选择: ↓ w=1+3=4为什么用两个堆？
单个堆的问题：
如果只用一个按利润排序的最大堆：
- 需要检查堆顶项目是否可做（资本是否足够）
- 如果不可做，需要取出、暂存、继续检查下一个
- 最坏情况：每轮要检查所有项目
双堆的优势：
- 资本堆：按资本排序，O(1) 判断是否有新项目解锁
- 利润堆：只存放可做的项目，堆顶一定可做且利润最高
每个项目最多进入两个堆各一次，总时间 O(n log n)。
复杂度分析
时间复杂度：O((n + k) log n)
- 初始化资本堆：O(n log n)
- 每个项目最多从资本堆移动到利润堆一次：O(n log n)
- 最多做 k 个项目：O(k log n)
空间复杂度：O(n)
- 两个堆共存储 n 个项目
边界情况
javascript
// 测试用例
findMaximizedCapital(1, 0, [1,2,3], [1,1,2]); // 初始资本不够 → 0
findMaximizedCapital(10, 0, [1,2,3], [0,1,1]); // k > n → 6
findMaximizedCapital(2, 0, [], []); // 空数组 → 0
findMaximizedCapital(1, 1000000000, [1], [0]); // 大资本 → 1000000001常见错误
1. 忘记提前终止
javascript
// ❌ 错误：没有检查是否有可做的项目
for (let i = 0; i < k; i++) {
// 如果 profitHeap 为空，extract() 可能出错
w += profitHeap.extract();
}
// ✅ 正确：检查并提前退出
if (profitHeap.size() === 0) {
break;
}2. 堆的排序方向错误
javascript
// ❌ 错误：资本堆用最大堆
const capitalHeap = new MaxHeap((a, b) => a[0] - b[0]);
// 这样会先取出资本要求最高的项目
// ✅ 正确：资本堆用最小堆，先处理资本要求低的
const capitalHeap = new MinHeap((a, b) => a[0] - b[0]);3. 资本和利润搞混
javascript
// ❌ 错误：把资本当利润加
w += capital[i];
// ✅ 正确：加的是利润，不是资本要求
w += profit;变体问题
如果每个项目可以做多次？
需要记录每个项目做过的次数，每次完成后把它重新加入堆。
如果项目有时间限制？
需要加入时间维度，可能需要用到线段树或其他数据结构。
如果需要输出选择的项目序列？
在利润堆中存储项目索引，选择时记录下来。
相关题目
| 题目 | 难度 | 关联点 |
|---|---|---|
| 1642. 可以到达的最远建筑 | 中等 | 贪心 + 堆 |
| 630. 课程表 III | 困难 | 贪心 + 最大堆 |
| 857. 雇佣 K 名工人的最低成本 | 困难 | 贪心 + 堆 |
小结
本题展示了贪心 + 双堆的经典模式：
- 贪心策略：每步选择局部最优（利润最高的可做项目）
- 双堆设计：
- 一个堆管理"候选池"（按条件排序）
- 一个堆管理"可选项"（按优先级排序）
- 动态解锁：随着状态变化（资本增加），项目从候选池流入可选池
核心技巧：
- 当需要在某个条件下选择最优时，考虑用堆
- 当条件会动态变化时，考虑用两个堆分离"等待"和"可选"
- 这种模式可以推广到很多"有条件的贪心选择"问题