看到“IPO”这个题名第一次刷 LeetCode 的人通常会以为要补一堆金融知识其实它就是一道非常经典的贪心 优先队列题。我当年在面试里也遇到过几乎一样的变形你是手握一笔初始资金的投资人每个项目有自己的启动门槛和预期收益最多投 k 个项目怎么投才能让最终手里的钱最多。LeetCode 502 把这个问题包装成了公司上市前的资本运作场景但剥掉外壳核心是“动态可达集合里选最优”的贪心决策模型。这道题很适合作为优先队列的进阶练习题因为它不像 Top K 问题那样直接让你用堆而是要你自己想到用堆去维护“当前能做的项目里利润最大的那个”。这道题的难点有两个一是能不能看穿贪心策略二是能不能把“每次都要重新找可做项目”这个过程优化到 O((n k) log n)。这篇文章我会从暴力模拟讲起因为先把正确解写出来再去优化是刷算法题最稳的路径。然后再给标准解法“排序 大顶堆”附 C 和 Python 双版本代码最后把边界情况、面试表述和一些延伸题目都过一遍。1. 先把这个题彻底读透IPO 到底在考什么1.1 原题描述与示例题目给了两个长度相同的数组profits和capitalprofits[i]表示第 i 个项目的纯利润capital[i]表示启动这个项目至少需要多少资本。你初始有w资本最多能完成k个项目。规则是只要当前资本w capital[i]就可以做第 i 个项目做完后资本变成w profits[i]然后这个项目不能重复做。问最终能获得的最大资本是多少。举个例子k 2, w 0, profits [1, 2, 3], capital [0, 1, 1]。初始资金是 0所以只能做项目 0门槛 0利润 1。做完后w 1此时项目 1 和项目 2 都解锁了它们利润分别是 2 和 3选利润更大的项目 2做完后w 4。最终答案是 4。如果你第一步就贪心地选一个当前做不了的项目那什么都做不成。这题返回值是最终资本不是最大利润总和所以每一步的收益会直接影响后续可选项目集合这是它和“背包问题”最大的区别背包的容量是固定的这里你的“容量”会因为选择而变化而且是单调增加的。1.2 为什么这不是一道简单排序题很多人第一反应是“把项目按利润从大到小排个序从前往后做不就行了”。这个思路在“所有项目一开始都能做”的条件下成立但本题里项目有门槛一个利润 100 但要求启动资金 200 的项目在你只有 50 资金时就是不可达的。等你能做到它时可用的项目可能已经变了。按资本门槛排序呢也不行。假设w 1, k 2项目 A 门槛 1 利润 1项目 B 门槛 2 利润 100项目 C 门槛 2 利润 99。按门槛排序你会先做 A得到w 2然后可以做 B最终w 102。这个例子里按门槛排序恰好是对的但如果项目 A 变成门槛 1 利润 0项目 B 是门槛 1 利润 5项目 C 是门槛 6 利润 100按门槛排序要先从门槛 1 的项目里选一个做这时候必须选利润更大的 B否则做完 A 还是只有 1做不了 C。所以关键不是“按门槛排完就顺序做”而是在每一个“当前资金”下从所有可达项目里挑利润最大的那个。这也是题目的核心模型你有多个阶段每个阶段开始时资金决定了一个可达项目集合你要从这个集合里挑一个项目执行然后资金增加解锁更多项目进入下一阶段。“每一步都在当前可达集合里选最优”正是贪心策略可以落地的场景。1.3 题目给你的隐藏信息题目里有一个容易被忽略的好性质做完一个项目后资金只会增加或不变题目默认利润非负不会减少。因为资金单调不减所以“可达项目集合”只会越来越大不会越来越小。这个单调性非常关键它意味着我们不需要每轮重新检查所有项目是否可达而是可以用一个指针按资本门槛从小到大推进把新增可达项目不断“解锁”出来。另一个隐藏信息是项目不能重复做。如果你用“把所有项目按利润放进堆里每轮取出利润最大的”这种做法很可能会重复取出同一个项目。所以标准做法里要维护一个“尚未完成”的候选池从堆里弹出项目后这个项目就不该再回到堆里。我见过好几个同学在这上面翻车最后算出来的资本比正确答案大很多。k 和 n 的关系也要注意。题目里 k 是最多能做的项目数不一定等于数组长度。当所有可达项目都做完了但还没达到 k 时就直接停止返回当前资金。这个“提前终止”的逻辑很多暴力版本容易漏掉它会直接影响时间复杂度分析和正确性。2. 思路一暴力模拟先把正确解写出来2.1 第一版代码每轮全量扫描最朴素的思路就是模拟真实投资过程每一轮开始扫一遍所有还没做的项目找出所有capital[i] w的项目里profits[i]最大的那个做掉它更新资金然后继续下一轮。直到已经做了 k 个项目或者没有可做项目为止。// 第一版暴力模拟时间复杂度 O(k * n) class Solution { public: int findMaximizedCapital(int k, int w, vectorint profits, vectorint capital) { int n profits.size(); vectorbool done(n, false); for (int round 0; round k; round) { int bestIdx -1; int bestProfit 0; // 题目利润非负 for (int i 0; i n; i) { if (done[i]) continue; if (capital[i] w profits[i] bestProfit) { bestProfit profits[i]; bestIdx i; } } if (bestIdx -1) break; // 没有可做项目了 done[bestIdx] true; w bestProfit; } return w; } };这段代码虽然效率不高但它对应的是题目的原始描述不容易写错。几个细节需要注意bestProfit初始值设 0因为题目规约利润非负这样“找不到可做项目”和“找了一个利润为 0 的项目”可以区分开done数组用来标记项目是否已经被做过避免重复选择。2.2 暴力做法的复杂度账每做一轮都要遍历所有 n 个项目选出利润最大的可达项目所以单轮时间复杂度是 O(n)。最多做 k 轮总时间复杂度 O(k * n)。当 n 和 k 都到 10^5 量级时最坏情况是 10^10 次比较这个量级在 OJ 上不可能过。但暴力版的正确性还是能保证的至少对一个小数据集的测试用例是没问题的。刷题时先把暴力写出来有一个好处你可以用它做“对拍”验证优化版本和暴力版本在小随机数据上的输出是否一致。我个人的刷题习惯是如果一道题一时半会儿想不出最优解先写一个能过的朴素版本再拿它当参照物这样后面优化时心里有底。2.3 从暴力里看到优化的钥匙暴力每一轮都在重复做同一件事扫描全数组找“可达且利润最大”。问题在于随着资金增加可达项目集合越来越大但暴力不管资金怎么变每次都从零开始扫这就浪费了大量重复计算。优化的突破口有两个。第一项目按资本门槛排序后我们可以只用一个指针不断往后推进把新解锁的项目找出来那些之前已经判断过“门槛大于当前资金”的项目在资金涨上去之后才需要重新检查但排序后指针就不回头所以每个项目最多被检查一次。第二已经解锁的项目需要一个数据结构来快速取出最大利润这个数据结构就是大顶堆。这两个想法组合起来就是标准解法。3. 思路二排序 大顶堆标准解法完整推导3.1 核心数据结构资金门槛排序列表与利润大根堆标准解法用到了两个关键结构按capital[i]升序排序的项目列表。排序后我们可以用一个指针从左往右扫把所有capital[i] w的项目“解锁”出来。因为资金只增不减这个指针永远不需要回退每个项目只会被解锁一次。一个大顶堆available用来存放所有已经解锁、还没做的项目的利润。每次解锁一批新项目后堆顶就是当前所有可达项目里利润最大的那个。从堆顶取项目做掉资金增加然后再解锁下一批。为什么是大顶堆而不是别的东西因为我们需要反复做两类操作插入一个“新解锁的项目”、取出“当前最大值”。大顶堆的插入和删除堆顶都是 O(log n)足够快。如果用一个有序数组维护虽然取出最大值是 O(1)但插入一个元素需要 O(n) 时间如果用普通数组插入 O(1) 但取最大值要 O(n) 扫描。堆正好是这两者之间的平衡点也是“动态集合中反复找最值”问题的最常用工具。3.2 C 实现class Solution { public: int findMaximizedCapital(int k, int w, vectorint profits, vectorint capital) { int n profits.size(); vectorpairint, int projects; // {capital, profit} for (int i 0; i n; i) { projects.emplace_back(capital[i], profits[i]); } sort(projects.begin(), projects.end()); priority_queueint pq; // 大顶堆存利润 int idx 0; for (int round 0; round k; round) { // 把所有当前资金能启动的项目解锁 while (idx n projects[idx].first w) { pq.push(projects[idx].second); idx; } if (pq.empty()) break; // 没有可做项目 w pq.top(); pq.pop(); } return w; } };这段代码非常短但要理解每一行为什么存在。projects.emplace_back(capital[i], profits[i])把资本和利润绑定在一起排序而不是分别存两个数组否则排序后你还要维护两个数组之间的对应关系比较容易错。sort默认按 pair 的第一个元素升序第一个元素相同则按第二个元素升序这种情况不影响正确性。while循环负责解锁新一轮资金能做的项目解锁条件用的是当前w因为在堆里已经做了某个高利润项目后w会变大下一轮while自然会把更多项目放进堆。3.3 Python 实现Python 的标准库heapq默认是小顶堆所以存利润时要把利润取负数取出时再取负回来。逻辑和 C 版本完全一致import heapq class Solution: def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) - int: n len(profits) projects sorted(zip(capital, profits)) pq [] # 大顶堆存负利润 idx 0 for _ in range(k): while idx n and projects[idx][0] w: heapq.heappush(pq, -projects[idx][1]) idx 1 if not pq: break w -heapq.heappop(pq) return w这里有一个很容易踩的坑Python 直接用heapq.heappush(pq, -profit)时如果两个项目利润相同堆里会先弹出哪个这不影响最终结果因为利润相同的项目带来的收益一样。但如果你要复现“和 C 完全一致”的执行过程就不要指望它按项目 id 排序了。3.4 复杂度与代码细节排序部分时间复杂度 O(n log n)。随后最多执行 k 轮每一轮会有一个while循环解锁项目整个算法里每个项目最多被push一次所以总的push次数是 O(n)总的pop次数是 O(k)。每轮堆操作 O(log n)总时间复杂度 O((n k) log n)。空间复杂度是 O(n)主要花在排序列表和堆上。第 19 行C 的if (pq.empty()) break;是最容易被忽略的一处。如果当前资金不足以解锁任何新项目而且堆里也没有已经解锁但未做的项目说明你已经做到做无可做的地步了再循环下去只会空转。这个 break 和暴力版的bestIdx -1是同一个逻辑但用堆实现时代码短了很多需要你自己意识到这个终止条件存在。4. 贪心为什么是对的一次严格的证明4.1 交换论证选最大利润项目永远不会亏面试时你说“每轮选当前能做且利润最大的项目”面试官通常会追问一句为什么贪心是对的这里可以用交换论证来回答。假设在某一步你的资金是 w当前可达项目集合是 S。设最优解在这一步选择了项目 a而贪心策略选择了项目 bb 是 S 中利润最大的项目所以有profit[b] profit[a]。现在我们在最优解里把 a 换成 b其他后续选择都不变。由于 b 的利润不小于 a 的利润做完 b 后的资金w profit[b]不少于做完 a 后的资金w profit[a]。后续最优解里原本安排的每个项目既然在资金w profit[a]下能做那么在资金w profit[b]下也一定能做因为资金更多门槛更容易满足。所以替换后的方案不会比原最优解差。每一轮都做这种替换最终可以证明贪心解等于某个最优解。这个证明的成立依赖两个前提项目之间没有依赖关系以及资金单调不减。如果某个项目做掉后会导致其他项目不可做这个论证就失效了但本题没有这种约束。4.2 边界推演为什么指针只扫一遍就够标准解法里有个细节while (idx n projects[idx].first w)这个循环为什么不在外层 for 循环的一开始把所有小于当前 w 的项目都 push 进去因为 push 完一批后w 可能因为做项目而变大会解锁更多所以 while 必须放在每一轮里用最新 w 去解锁。但为什么整个算法里idx不用回退因为projects按capital升序排列后如果某个项目的门槛大于当时的 w那么它后面的项目门槛只会更大也不可达而当 w 变大以后我们再从当前idx继续往后检查之前已经检查过的项目都已经解锁过了不需要重新检查。这个“指针单调向右”的性质保证了每个项目只被判断一次时间复杂度才能压到 O(n log n)。如果不想排序用另一个小顶堆存{capital, profit}每轮从这个小顶堆里弹出所有capital w的项目也可以达到类似效果但每次都要重构堆或重复弹出逻辑没有排序后指针扫描清晰所以实战中我更喜欢排序 单指针。4.3 一个反直觉的例子我再给一个例子说明“看似收益差不多的项目交错选择可能差异很大”。设w 2, k 2项目 A门槛 1利润 2项目 B门槛 2利润 3项目 C门槛 4利润 10。按贪心第一轮资金 2可做 A 和 BB 利润 3 最大做 Bw 5第二轮做 Cw 15。如果第一轮贪心地做 A因为 A 门槛低容易被先注意到w 4第二轮只能做 Cw 14。只差 1但方向错了。这个例子也说明门槛低的项目不一定先做只有“在可达集合里利润最大”的项目才值得先做。这道题里没有“必须先做低门槛项目来解锁高门槛项目”的硬性前提因为只要资金够了高门槛项目自然解锁而做低门槛低利润项目反而浪费了一轮机会拉低了资金增长的速度。5. 实战中的边界情况与排查技巧5.1 边界 case 速查表我在本地调试这道题时会准备一组典型输入覆盖最常见的坑。场景输入示例预期结果说明初始资金做不了任何项目k3, w5, profits[1,2], capital[6,7]5直接返回初始资金可做项目数不足 kk5, w1, profits[1], capital[0]2做完唯一项目后就 break有利润为 0 的项目k2, w0, profits[0,5], capital[0,0]5先做利润 5 的0 利润项目做不做不影响结果门槛全部为 0k2, w0, profits[3,1], capital[0,0]4等价于从所有项目里按利润从大到小取 k 个高利润高门槛项目最后才解锁k1, w1, profits[100], capital[2]1只有一轮做不了门槛 2 的项目这些 case 我在 LeetCode 提交前都会先跑一遍。尤其是一个容易混淆的地方如果一个利润为 0 的项目是当前唯一可达项目那么做了它资金不变下一轮它的可达集合也不会变大所以它本质上是一个“可做可不做”的项目。算法里因为堆空会导致 break所以不会死循环。5.2 语言层面的坑C 优先队列默认是大顶堆priority_queueint取堆顶是top()后pop()不要和栈的top搞混。Python 的heapq是小顶堆必须存负值而且heappop返回的是负数要记得再取一次负号。如果利润和资本可能很大比如题目范围扩展到 10^9w profit可能溢出 int。保险的做法是用long long。LeetCode 原题里 int 一般够用但面试手写时我会直接用 long long省得在边界被问翻。还有一个我踩过的坑vectorpairint,int projects排序时如果两个项目的资本一样会按利润升序排。这没问题因为while会把所有资本小于等于 w 的项目一次性全部 push 进堆和它们在数组里的相对顺序无关。但如果你在while内部做的是“push 一个就 pop 一个”那就需要注意顺序了好在标准解法不做这种操作。5.3 面试现场怎么说这道题在面试里出现时我建议按这个顺序表达先复述题意确认 k、w、profits、capital 的含义问清楚项目是否可以重复做。通常不能重复做。说一句“这题可以用贪心 优先队列。每轮我们只需要从所有能启动的项目里选利润最大的因为利润越大后续资金越多可达项目集合只会变大所以不会亏。”再讲数据结构项目按资本排序用大顶堆维护当前可达项目的利润。讲时间复杂度 O((n k) log n)空间 O(n)。最后跑一下题目给的示例甚至可以口头推演。这样讲比直接丢代码清晰很多。面试官如果追问“为什么贪心是对的”就把上一节的交换论证讲出来。我见过不少候选人卡在“知道用堆但说不清为什么”代码写完但解释含糊这很可惜。6. 题型变体与延伸练习6.1 同一思路的其他题“排序 优先队列每轮解锁一批候选从中取最优”这个套路在 LeetCode 里出现频率很高典型的有LeetCode 630 课程表 III每门课有持续时间和截止时间最多能上多少门课。这题也是先按截止时间排序用小顶堆维护已选课程的持续时间超过截止时间时就弹出耗时最长的课本质是“在解锁的候选里淘汰代价最大”。LeetCode 871 最低加油次数沿途每个加油站能加一定油量求最少加油次数到达终点。每次经过加油站就把油量加入大顶堆油不够时从堆里取最大的油和 IPO 的“解锁 取最大”可以说是一个模子。LeetCode 1353 最多可以参加的会议数目每天只能参加一个会议每个会议有开始和结束时间按开始时间排序每一天把当天开始的会议加入堆然后参加结束时间最早的会议。这对应的是“候选集合动态变化”的另一个应用方向。刷完这四道题你会对“为什么很多最优解问题要配一个优先队列”有比较深的体感因为这些问题都需要在动态变化的候选集合里快速做出某种“极值选择”而堆就是为这种场景准备的数据结构。热门 100 题里的“合并 K 个升序链表”“数组中的第 K 个最大元素”也是优先队列考点但它们更偏向堆的基础用法。IPO 的价值在于它把堆和排序、贪心结合起来是一个综合题。6.2 从这道题看优先队列的刷题姿势如果你刚开始刷优先队列我建议不要只背 API而是先想清楚三个问题维护的集合是什么集合为什么是动态变化的每一步需要在集合里做哪种极值操作对 IPO 来说集合是“当前可达且未做的项目”变化原因是资金增加解锁新项目需要的操作是“取利润最大值”。想清楚这三件事代码自然就写出来了。还有一个小技巧解这类题时先手动推演一遍示例把“每轮解锁了哪些项目、堆里有哪些值、弹出哪个”记录下来。我刷题时经常在草稿纸上画这样一个三列表格轮次、解锁的项目、堆里的利润。IPO 这道题推演一遍基本就不会写错边界条件了。最后再分享一个我个人的体会这道题如果第一次见面没做出来不用沮丧因为“贪心 优先队列”的组合本来就需要多次见题才能形成条件反射。关键是做完之后把“当前可达集合中取最优”这个抽象模型记住。下次再遇到“每个阶段有新的候选、需要从中选一个最优”的题不管包装成投资、上课还是加油你都能第一时间想到堆。这个套路的价值远大于这一道题本身。
