LeetCode 502. IPO

2023-02-04 HGNULB 约 9 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 困难未解决 1-2 字节跳动面试经典 150 题

题目描述

✅ 502. IPO

题意分析

手上有初始资本 w，一共 n 个项目。第 i 个项目需要至少 capital[i] 的资本才能启动，完成后净赚 profits[i]——利润直接叠加到手上的资本上，本金不消耗。最多只能做 k 个项目，每个项目至多做一次，问最终资本的最大值。

最关键的一条隐藏性质是资本只增不减：profits[i] 非负，做完任何项目手头的钱都不会变少。因此「当前买得起的项目集合」只会往里加元素、永远不会往外删——做了某个项目绝不会让另一个项目变得启动不了。这条单调性直接抹掉了「为了将来放弃眼前」的取舍空间。

约束透露的信号：$n \le 10^5$ 且 $k \le 10^5$，两者同阶。这既排除了「每轮重新扫一遍全部项目」的平方级做法，也排除了把 k 当作状态维度的动态规划。可以接受的量级在 $O(n \log n)$ 附近，暗示要先按某个键把项目排好序，再配一个能反复取极值、支持增量插入的结构。

边界要注意三处：可启动集合为空时必须立刻停下，剩余轮次一个都做不了；k 可能大于 n，实际最多只能做 n 个；资本上界 $w \le 10^9$ 再叠加至多 $10^5 \times 10^4$ 的利润会突破 32 位有符号整数的范围，累加变量要留够位宽。

解法：双堆贪心

核心思路

先看暴力：每一轮都把 n 个项目从头扫一遍，挑出「资本要求不超过当前手头资本」里利润最大的那个，做掉并更新资本，如此重复 k 轮。正确性没有疑问，但每轮 $O(n)$、共 k 轮，总计 $O(nk)$，在 $10^5 \times 10^5$ 的规模下毫无希望。

瓶颈非常明确：每一轮都在重新扫描同一批项目，而其中绝大多数的可启动状态和上一轮完全一样。回到题意分析里那条单调性——资本只增不减，所以「已经买得起」的项目此后永远买得起。既然这个集合只增不减，就不该反复重算，而应该增量地维护。

用两个堆按状态分工：资本小顶堆 locked 保存尚未解锁的项目，堆顶是资本要求最低者；利润大顶堆 available 保存当前可做项目，堆顶是利润最大者。资本增长后，不断把 locked 中要求不超过当前资本的项目转移到 available。

小顶堆保证只检查堆顶就知道是否还有新项目能解锁；大顶堆保证每轮 $O(\log n)$ 取出当前最大利润。项目只会经历「未解锁 → 已解锁 → 已完成」三种状态，各移动一次。

贪心可用交换论证：若某个最优方案当前先选利润较小的可行项目 q，改为先选最大利润项目 p 后，资本只会更多，因此原方案后续能解锁的项目仍然都能解锁；q 仍留在候选中，可在后续替换 p 原本的位置。这样不会减少最终资本，逐轮取最大利润最优。

循环不变量是：每轮完成转移后，available 恰好包含所有资本要求不超过 cur 且尚未完成的项目，locked 包含其余项目；cur 是已完成项目后的资本。 弹出最大利润并累加后，不变量可在下一轮重新建立。

解题步骤

把每个 (capital[i], profits[i]) 放入资本小顶堆。两个数组必须作为一个项目整体保存；小顶堆按资本要求排序。

准备空的利润大顶堆，并令当前资本 cur = w。两个堆分别回答「下一批谁能解锁」和「已解锁项目里先做谁」。

循环最多 k 轮。为什么：每轮恰好做一个项目，做满 k 个就停；写成 for 而不是 while 可以让「最多 k 次」这个约束由循环结构天然保证。

每轮先解锁：只要资本堆非空且堆顶要求不超过 cur，就弹出该项目并把利润压入利润堆。堆顶都买不起时，其余锁定项目更买不起，可以停止转移。

堆为空则直接 break。为什么：堆空意味着现有资本连最便宜的项目都启动不了，而资本此后不会再增加，后续轮次永远是空转，继续循环只是浪费时间——注意这里不能 continue。

弹出堆顶并累加到 cur。为什么：堆顶是候选池中利润最大的项目；弹出同时完成了「记账」和「标记已做」两件事，天然避免同一个项目被选两次。

循环结束返回 cur。为什么：cur 从初始资本一路累加，任何时刻都等于「已完成项目后的资本」，不需要再单独维护一个答案变量。

以 k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1] 走一遍：资本堆含 (0,1)、(1,2)、(1,3)，利润堆为空。

第一轮只把 (0,1) 转入利润堆，弹出利润 1 后 cur = 1。

第二轮把剩余两个项目都转入利润堆，弹出最大利润 3，得到 cur = 4。两轮结束，返回 4。

代码实现

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        PriorityQueue<int[]> locked = new PriorityQueue<>(
                Comparator.comparingInt(project -> project[0]));
        for (int i = 0; i < profits.length; i++) {
            locked.offer(new int[] {capital[i], profits[i]});
        }
        PriorityQueue<Integer> available = new PriorityQueue<>(Comparator.reverseOrder());
        long cur = w;

        for (int i = 0; i < k; i++) {
            while (!locked.isEmpty() && locked.peek()[0] <= cur) {
                available.offer(locked.poll()[1]);
            }
            if (available.isEmpty()) {
                break;
            }
            cur += available.poll();
        }

        return (int) cur;
    }
}

import "container/heap"

type capitalMinHeap [][2]int

func (h capitalMinHeap) Len() int           { return len(h) }
func (h capitalMinHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h capitalMinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *capitalMinHeap) Push(x any)        { *h = append(*h, x.([2]int)) }
func (h *capitalMinHeap) Pop() any {
	old := *h
	last := old[len(old)-1]
	*h = old[:len(old)-1]
	return last
}

type profitMaxHeap []int

func (h profitMaxHeap) Len() int           { return len(h) }
func (h profitMaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h profitMaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *profitMaxHeap) Push(x any)        { *h = append(*h, x.(int)) }

func (h *profitMaxHeap) Pop() any {
	old := *h
	last := old[len(old)-1]
	*h = old[:len(old)-1]
	return last
}

func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
	locked := &capitalMinHeap{}
	for i := range profits {
		heap.Push(locked, [2]int{capital[i], profits[i]})
	}
	available := &profitMaxHeap{}
	cur := int64(w)

	for i := 0; i < k; i++ {
		for locked.Len() > 0 && int64((*locked)[0][0]) <= cur {
			project := heap.Pop(locked).([2]int)
			heap.Push(available, project[1])
		}
		if available.Len() == 0 {
			break
		}
		cur += int64(heap.Pop(available).(int))
	}

	return int(cur)
}

复杂度分析

时间复杂度：$O((n + \min(k,n))\log n)$，可写成 $O(n\log n)$。每个项目进入资本堆一次、转入利润堆一次，最多再被选出一次；有效轮次不超过项目数。

空间复杂度：$O(n)$。两个堆合计保存尚未完成的项目，数量不超过 n。

关键点总结

识别「资源单调不减」是这类贪心的钥匙：只要做某个选择不会关闭别的选项，就可以放心每步取最优，不必考虑回溯或权衡。面试时先把这句话说出来，等于直接给出了贪心的正确性证明。

两个堆的排序键不同：资本小顶堆决定什么时候能用，利润大顶堆决定优先用哪个。项目只单向转移，不需要每轮重扫。

小顶堆堆顶都无法解锁时，其余锁定项目一定也不行；利润堆为空则资本再也不会增长，必须直接结束。

堆的「弹出」同时承担了取最值和去重两个职责，天然满足「每个项目最多做一次」，不需要额外的 visited 数组。

当前约束下最终资本不超过 $2 \times 10^9$，仍在 32 位有符号范围内；实现内部用 64 位累加更稳妥，最后按方法签名转回整数。

提前 break 不只是优化：k 远大于 n 时，没有 break 会让循环空转 $10^5$ 次。能讲清「为什么此处是 break 而不是 continue」说明真的理解了单调性。

易错点总结

资本堆只存资本、不携带对应利润：项目配对关系丢失，解锁后无法知道该把哪个利润放入候选堆。

资本堆按利润而不是资本要求排序：堆顶可能是高利润但暂不可做的项目，导致算法看不到堆中其他已经可做的项目。

堆空时写 continue 而不是 break：k = 100000, w = 0, capital 全部大于 0 → 循环空转十万轮，每轮还要重新判一次堆空，超时。

把解锁的 while 写成 if：w = 0, capital = [0, 0, 0], profits = [1, 5, 3], k = 1 → 一轮只转入一个项目，可能返回 1 而不是 5。

用最小堆或忘记反转比较器：Java 写成 new PriorityQueue<>()、Go 写成 h[i] < h[j] → 每轮拿走的是利润最小的项目，profits = [1, 5], capital = [0, 0], w = 0, k = 1 会返回 1 而不是 5。

解锁条件写成 locked.peek().capital < cur：w = 1, capital = [1], profits = [10], k = 1 → 资本恰好等于要求的项目被漏掉，返回 1；条件必须包含等号。

循环以“还有锁定项目”为条件而忽略 k：可能连续完成超过 k 个项目；外层必须严格控制最多选择 k 次。

每轮重建两个堆：结果可能仍正确，但复杂度退回近似 $O(nk)$；项目状态应跨轮增量维护。

相似题目

题目	难度	考察点
1642. 可以到达的最远建筑	中等	同样是「先都用便宜方案，再用堆反悔」，堆里存的是已花掉的代价而非未来收益
871. 最低加油次数	困难	油量代替资本，堆里存沿途已错过的加油站，缺油时回头补加，是反悔贪心的典型
630. 课程表 III	困难	按截止时间排序后，超时就从堆里踢掉耗时最长的课，取最值的方向是「淘汰」
2542. 最大子序列的分数	中等	按 `nums2` 降序枚举最小值，用最小堆维护 `nums1` 的前 `k` 大，双键各管一维
253. 会议室 II	中等	按开始时间排序 + 最小堆维护结束时间，堆的大小本身就是答案
1046. 最后一块石头的重量	简单	纯大顶堆模拟，没有排序与解锁指针，可当作本题堆操作部分的最小练习
373. 查找和最小的 K 对数字	中等	堆中元素由上一次弹出的结果动态派生，扩展方式比本题的顺序解锁复杂
621. 任务调度器	中等	贪心对象是频次而非收益，冷却期让「取最大」变成按轮次批量取，可用公式直推