LeetCode 502. IPO

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 面试经典 150 题 字节
标签
数组 排序 贪心 堆（优先队列）

题目描述

✅ 502. IPO

image-20260929100729480

image-20260929100729586

题意分析

初始资本为 w，最多完成 k 个不同项目。capital[i] 只是启动门槛，完成项目后增加的是 profits[i]，不用扣除门槛本身。利润非负，求最终能拥有的最大资本。

当前能做哪些项目取决于资本，选哪个项目取决于利润。分别按门槛和利润维护两个堆，就能在资本增长后找到新解锁项目，再从所有可行项目中选择收益最大的一个。

解法：双堆贪心

核心思路

[!blue]
两个堆分别维护可行性与选择优先级。 locked 是资本门槛小顶堆，每项保存门槛和利润；available 是利润大顶堆，保存已经可做但尚未完成的项目；cur 是当前资本。利润非负，资本只会不变或增加，因此已解锁项目不会重新变得不可做。

每轮先把 locked 中门槛不超过 cur 的项目全部转入 available。小顶堆堆顶是最小门槛，堆顶尚不可做时，其余项目也都不可做；转移完后，利润堆就覆盖了当前的全部可行选择。

设利润堆中最大利润项目为 g，某个最优方案先做 a。若方案从未选择 g，用 g 替换 a 后，后续每一步的资本都不会减少；若方案稍后才做 g，交换 a、g 的次序，交换位置之前的资本只会更多，之后的总利润相同，而延后的 a 原本在初始资本下就能启动。两种情况都不会破坏后续可行性，所以总存在先做 g 的最优方案，剩余轮次可以重复同样的选择。

弹出利润堆顶表示完成这个项目，随后把利润加入 cur。每个项目从门槛堆移出一次、从利润堆完成一次，不会重复选择。利润堆为空时没有办法再增加资本，直接结束；否则最多执行 k 轮。题目保证最终答案能放入有符号 32 位整数，代码用更宽的类型累计后再返回。

解题步骤

  1. 全部项目按资本要求进入小顶堆。
  2. 每轮将所有已满足门槛的项目转入利润堆。
  3. 利润堆为空则结束，否则弹出最大利润累加。
  4. 最多完成 k 轮，返回当前资本。

代码实现

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+1))$，每个项目只经过固定次数堆操作。
  • 空间复杂度：$O(n)$，两个堆保存尚未完成的项目。

关键点总结

[!green]

  • 资本要求是门槛，不是支出。
  • 每轮先完整解锁，再从可行项目中挑最大利润。
  • 弹出项目意味着完成，后续不能重复选择。

易错点总结

[!yellow]

  • 资本堆按利润排序：堆顶买不起时可能遮住其他可做项目。
  • 只转移一个已解锁项目：可能漏掉同轮更高利润选择。
  • 门槛用严格小于：资本恰好足够也应允许。
  • 利润使用小顶堆：每轮选择成最小收益。

相似题目

题目 难度 关联与区别
871. 最低加油次数 困难 同样维护当前资源门槛内可选的项目，并优先取最大收益扩大后续可达范围。
630. 课程表 III 困难 同样先按约束排序再用堆做贪心，但原题淘汰耗时最长者，本题选择收益最大者，目标与堆含义不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/19708323
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！