IPO 图解题解

这道题到底在问什么

k / w

3 / 0

profits

[2,5,8,3,6]

capital

[0,1,2,3,4]

输出

16

最优解：一步一步想明白

1. 3两件事配合:① 把项目按门槛 capital 升序排好,本金涨了就把新够得着的「解锁」进候选池;② 候选池用大根堆装利润,随时一秒取出最大的那个,不用每轮重新扫。
2. 4盯住下面三样怎么变:指针 ptr(沿排好序的项目往右推,负责解锁)、大根堆(装解锁项目的利润,堆顶永远最大)、本金 w(每取一个堆顶就涨一次)。
3. 5本金 w=0,还能做 k=3,ptr 待出发项目按门槛 capital 从小到大排好(本例 capital=[0,1,2,3,4] 已升序)。指针 ptr 从最左开始,只往右走,把本金够得着的项目利润送进大根堆。本金 0,还能做 3 个。
4. 6ptr=0:门槛 c0=0 ≤ 0 → 解锁项目0指针停在项目 0:门槛 0,本金 0 够得着,把它利润 2 送进堆。再看项目 1,门槛是 1,本金不够,指针就先停在这,等本金涨了再往右。
5. 7堆里现在:[2]候选池(大根堆)里现在只有一个利润 2。堆顶永远是当前能做的项目里利润最大的——现在就它一个。
6. 8pop 堆顶 2 → w = 0 + 2 = 2从堆顶取出利润 2 做掉,本金从 0 涨到 2。堆空了。关键:本金一变大,原本够不着的项目可能解锁了——下一轮先回去推指针补充候选。
7. 9ptr 推进:c1=1 ≤ 2 → 解锁项目1本金涨到 2,指针往右推。项目 1 门槛 1,够得着,利润 5 入堆。项目 0 已用过(灰)。本金 2 还够不够下一个?继续看。
8. 10堆里现在:[5]利润 5 进堆,成为新堆顶。但解锁阶段还没结束——本金 2 也够得着门槛为 2 的项目 2,接着把它也解锁进来,再决定取谁。
9. 11ptr 再推进:c2=2 ≤ 2 → 解锁项目2本金 2 也够得着门槛 2 的项目 2,利润 8 一起入堆。再看项目 3,门槛 3,本金不够,指针停下。这一轮一口气解锁了两个项目,候选池里有两个了。
10. 12新元素 8 先放末尾:[5, 8]入堆分两步。第一步:新利润 8 先塞到堆的最末尾(成为 5 的孩子)。这时堆顶暂时还是 5,但 8 比父亲大,违反了大根堆的规矩,接下来要让它往上「冒泡」。
11. 138 与父亲 5 交换,冒到堆顶:[8, 5]第二步「上浮」:新来的 8 和父亲 5 比,8 更大就交换,一路往上冒,直到比父亲小或到顶。这里 8 一步就冒到了堆顶,5 沉下去当它的孩子。这就是堆维持「堆顶最大」的内部动作。
12. 14pop 堆顶 8 → w = 2 + 8 = 10取出堆顶 8 做掉,本金 2 → 10!利润 5 没被取走,继续留在堆里当候选。本金涨到 10,后面门槛更高的项目这下也够得着了。
13. 15ptr 推进:c3=3 ≤ 10 → 解锁项目3本金 10 远超剩下项目的门槛。指针先推到项目 3(门槛 3),利润 3 入堆。还有项目 4 没看,接着推。
14. 16堆里现在:[5, 3],堆顶=5利润 3 进堆,但它比堆顶 5 小,沉到 5 下面当孩子,5 仍是堆顶。本金 10 还够得着最后的项目 4,继续解锁。
15. 17ptr 再推进:c4=4 ≤ 10 → 解锁项目4项目 4 门槛 4,本金 10 够得着,利润 6 入堆。指针走到末尾,所有项目都解锁完了,以后不再回头。
16. 18新元素 6 放末尾:[5, 3, 6]和刚才一样:新利润 6 先挂到堆的最末尾。它的父亲是堆顶的 5。6 比父亲 5 还大,又违规了,所以下一帧要让 6 往上冒。
17. 196 与父亲 5 交换:[6, 3, 5],堆顶=66 和父亲 5 交换,6 上浮成新堆顶,5 沉下去当孩子,3 没动。现在候选池里有 6、5、3 三个,堆顶是 6。最后一个名额该花在它身上。
18. 20拿走 6,末尾 5 补到堆顶:[5, 3]取堆顶不是简单删掉:先把堆顶 6 拿走,再把末尾的 5 搬到堆顶补空,然后让它和孩子比、必要时一路「下沉」。这里 5 比孩子 3 大,停在顶上,堆依然合法。
19. 21本金 10 + 6 = 16,k 用完取出堆顶 6,本金 10 → 16。这是第 3 个项目,k 用完了,循环结束。堆里还剩利润 5、3 的项目虽做得起,但名额没了——这正是贪心:把有限的 k 个名额砸在最值钱的项目上。
20. 22本金轨迹 0 → 2 → 10 → 16整道题就这个循环:本金涨了就推指针解锁新项目入堆,再从堆顶取利润最大的做掉。绿勾标出真做的三个(利润 2、8、6),本金一路涨到 16,和手算一致。
21. 23别贪「门槛最低」或「最先解锁」的——解锁只决定能不能做,真正决定收益的是利润。一旦解锁,就该在所有候选里挑利润最大的,这才让本金涨最快、解锁更多项目。
22. 24O(k·n) → O((n+k)·log n)核心提速:用大根堆替代每轮重扫。每个项目一生只进堆一次、出堆一次,取最大利润只要 O(log n),不再做重复劳动。
23. 28本金不够解锁任何项目 → 堆为空如果某一轮一个项目都解锁不了,堆就是空的。这时必须 break 提前结束,不能硬去取堆顶,否则会对空堆操作报错。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import heapq
class Solution:
    def findMaximizedCapital(self, k, w, profits, capital):
        n = len(profits)
        projects = sorted(zip(capital, profits))  # 按资本升序
        heap = []          # 取负利润压小根堆,模拟大根堆
        ptr = 0
        for _ in range(k):
            while ptr < n and projects[ptr][0] <= w:  # 解锁
                heapq.heappush(heap, -projects[ptr][1])
                ptr += 1
            if not heap:   # 没有能做的项目,提前结束
                break
            w -= heapq.heappop(heap)   # 取最大利润加到 w
        return w

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<pair<int,int>> projects(n);
        for (int i = 0; i < n; i++) projects[i] = {capital[i], profits[i]};
        sort(projects.begin(), projects.end());  // 按资本升序
        priority_queue<int> heap;   // 大根堆:利润
        int ptr = 0;
        for (int t = 0; t < k; t++) {
            while (ptr < n && projects[ptr].first <= w) {  // 解锁
                heap.push(projects[ptr].second);
                ptr++;
            }
            if (heap.empty()) break;
            w += heap.top(); heap.pop();   // 取最大利润
        }
        return w;
    }
};

import java.util.*;
class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        Arrays.sort(projects, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) { return a[0] - b[0]; }
        });
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        int ptr = 0;
        for (int t = 0; t < k; t++) {
            while (ptr < n && projects[ptr][0] <= w) {  // 解锁
                heap.offer(projects[ptr][1]);
                ptr++;
            }
            if (heap.isEmpty()) break;
            w += heap.poll();   // 取最大利润
        }
        return w;
    }
}

复杂度

面试官可能追问