Hard

题目描述

假设 LeetCode 即将开始 IPO。为了以更高的价格将股票卖给风险投资公司，LeetCode 希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 LeetCode 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目，其中第 i 个项目有纯利润 profits[i] 和启动该项目需要的最小资本 capital[i]。

最初，你的资本为 w。当你完成一个项目时，你将获得纯利润，利润将被添加到你的总资本中。

总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可以获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：由于你的初始资本为 0，你只能从第 0 个项目开始。
在完成后，你将获得利润 1，你的总资本将变为 1。
此时，你可以选择开始第 1 个或第 2 个项目。
由于你最多可以选择两个项目，所以你需要完成第 2 个项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

提示：

  • 1 <= k <= 10^5
  • 0 <= w <= 10^9
  • n == profits.length
  • n == capital.length
  • 1 <= n <= 10^5
  • 0 <= profits[i] <= 10^4
  • 0 <= capital[i] <= 10^9

解题思路

这是一道经典的贪心 + 堆的问题。核心思路是：在每一步选择当前能够承担的项目中利润最大的那个。

解题步骤：

  1. 数据预处理：将每个项目的资本和利润打包，按照启动资本从小到大排序。这样我们可以依次检查哪些项目是当前资本可以承担的。

  2. 贪心策略：在每一轮中，我们需要：

    • 将所有当前资本可以承担的项目加入到一个最大堆中（按利润排序）
    • 从最大堆中取出利润最大的项目执行
    • 更新当前资本

  3. 使用优先队列优化：

    • 用最小堆存储按资本排序的项目
    • 用最大堆存储当前可执行的项目（按利润排序）

算法流程：

  • 初始化两个堆：项目堆（按资本排序）和利润堆（按利润排序）
  • 重复k次或直到没有可执行项目：
    • 将所有资本要求 <= 当前资本的项目移入利润堆
    • 如果利润堆为空，说明无法继续执行项目，退出
    • 否则取出利润最大的项目，更新资本

这种方法保证了每次都选择当前能够执行的项目中利润最大的，符合贪心策略的最优性。

代码实现

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<pair<int, int>> projects;
        
        // 将项目按启动资本排序
        for (int i = 0; i < n; i++) {
            projects.push_back({capital[i], profits[i]});
        }
        sort(projects.begin(), projects.end());
        
        // 最大堆存储可执行项目的利润
        priority_queue<int> profitHeap;
        int i = 0;
        
        for (int j = 0; j < k; j++) {
            // 将所有可执行的项目加入利润堆
            while (i < n && projects[i].first <= w) {
                profitHeap.push(projects[i].second);
                i++;
            }
            
            // 如果没有可执行项目，退出
            if (profitHeap.empty()) {
                break;
            }
            
            // 执行利润最大的项目
            w += profitHeap.top();
            profitHeap.pop();
        }
        
        return w;
    }
};

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        import heapq
        
        n = len(profits)
        projects = [(capital[i], profits[i]) for i in range(n)]
        projects.sort()
        
        # 最大堆存储可执行项目的利润（Python用负数实现最大堆）
        profit_heap = []
        i = 0
        
        for _ in range(k):
            # 将所有可执行的项目加入利润堆
            while i < n and projects[i][0] <= w:
                heapq.heappush(profit_heap, -projects[i][1])
                i += 1
            
            # 如果没有可执行项目，退出
            if not profit_heap:
                break
            
            # 执行利润最大的项目
            w += -heapq.heappop(profit_heap)
        
        return w

public class Solution {
    public int FindMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.Length;
        var projects = new List<(int capital, int profit)>();
        
        // 将项目按启动资本排序
        for (int i = 0; i < n; i++) {
            projects.Add((capital[i], profits[i]));
        }
        projects.Sort();
        
        // 最大堆存储可执行项目的利润
        var profitHeap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
        int idx = 0;
        
        for (int j = 0; j < k; j++) {
            // 将所有可执行的项目加入利润堆
            while (idx < n && projects[idx].capital <= w) {
                profitHeap.Enqueue(projects[idx].profit, projects[idx].profit);
                idx++;
            }
            
            // 如果没有可执行项目，退出
            if (profitHeap.Count == 0) {
                break;
            }
            
            // 执行利润最大的项目
            w += profitHeap.Dequeue();
        }
        
        return w;
    }
}

var findMaximizedCapital = function(k, w, profits, capital) {
    const n = profits.length;
    const projects = [];
    
    for (let i = 0; i < n; i++) {
        projects.push([capital[i], profits[i]]);
    }
    
    projects.sort((a, b) => a[0] - b[0]);
    
    const maxHeap = [];
    
    function heapPush(val) {
        maxHeap.push(val);
        let i = maxHeap.length - 1;
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (maxHeap[parent] >= maxHeap[i]) break;
            [maxHeap[parent], maxHeap[i]] = [maxHeap[i], maxHeap[parent]];
            i = parent;
        }
    }
    
    function heapPop() {
        if (maxHeap.length === 0) return null;
        if (maxHeap.length === 1) return maxHeap.pop();
        
        const max = maxHeap[0];
        maxHeap[0] = maxHeap.pop();
        
        let i = 0;
        while (true) {
            const left = 2 * i + 1;
            const right = 2 * i + 2;
            let largest = i;
            
            if (left < maxHeap.length && maxHeap[left] > maxHeap[largest]) {
                largest = left;
            }
            if (right < maxHeap.length && maxHeap[right] > maxHeap[largest]) {
                largest = right;
            }
            
            if (largest === i) break;
            
            [maxHeap[i], maxHeap[largest]] = [maxHeap[largest], maxHeap[i]];
            i = largest;
        }
        
        return max;
    }
    
    let currentCapital = w;
    let projectIndex = 0;
    
    for (let i = 0; i < k; i++) {
        while (projectIndex < n && projects[projectIndex][0] <= currentCapital) {
            heapPush(projects[projectIndex][1]);
            projectIndex++;
        }
        
        if (maxHeap.length === 0) break;
        
        currentCapital += heapPop();
    }
    
    return currentCapital;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n + k log n)
空间复杂度O(n)

解释：

  • 时间复杂度：排序需要 O(n log n)，每次操作最多进行 k 次，每次堆操作为 O(log n)
  • 空间复杂度：存储项目信息和堆需要 O(n) 空间

相关题目