当前位置：首页 > article >正文

LeetCode题练习与总结：IPO--502

article 2025/1/1 5:14:21

一、题目描述

假设力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助力扣设计完成最多 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

二、解题思路

将所有项目按照所需的最小资本从小到大排序。
使用一个最大堆（优先队列）来存储所有可以启动的项目，并且按照利润从大到小排序。
每次从最大堆中取出利润最大的项目，如果当前资本不足以启动该项目，则跳过。
重复步骤3，直到完成k个项目或者没有可以启动的项目为止。

三、具体代码

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // 将项目按照所需的最小资本从小到大排序
        int[][] projects = new int[profits.length][2];
        for (int i = 0; i < profits.length; i++) {
            projects[i] = new int[]{capital[i], profits[i]};
        }
        Arrays.sort(projects, (a, b) -> a[0] - b[0]);

        // 最大堆，按照利润从大到小排序
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);

        int index = 0;
        for (int i = 0; i < k; i++) {
            // 将所有可以启动的项目加入最大堆
            while (index < projects.length && projects[index][0] <= w) {
                maxHeap.add(projects[index]);
                index++;
            }

            // 如果最大堆为空，说明没有可以启动的项目了，直接退出循环
            if (maxHeap.isEmpty()) {
                break;
            }

            // 从最大堆中取出利润最大的项目
            w += maxHeap.poll()[1];
        }

        return w;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

将所有项目按照所需的最小资本排序，时间复杂度为 O(n log n)，其中 n 是项目的数量。
对于每个项目，我们最多将其加入最大堆一次，并且在最大堆中最多删除一次。由于最大堆的操作（添加和删除）的时间复杂度为 O(log n)，所以对于 k 个项目的操作，总的时间复杂度为 O(k log n)。
将所有可以启动的项目加入最大堆，这个过程最多执行 n 次，每次操作的时间复杂度为 O(log n)，因此总的时间复杂度为 O(n log n)。

综上所述，总的时间复杂度为 O(n log n) + O(k log n) + O(n log n) = O(n log n)，因为 k ≤ n。

2. 空间复杂度

创建了一个二维数组 projects 来存储项目和它们对应的资本和利润，空间复杂度为 O(n)。
使用了一个最大堆 maxHeap 来存储可以启动的项目，在最坏的情况下，所有项目都可以启动，因此最大堆的大小最多为 n，空间复杂度为 O(n)。

综上所述，总的空间复杂度为 O(n) + O(n) = O(n)。

五、总结知识点

数组与二维数组：
- 使用二维数组 projects 来存储每个项目的资本和利润。
排序：
- 使用 Arrays.sort 方法对二维数组进行排序，根据每个项目的资本需求从小到大排序。
优先队列（最大堆）：
- 使用 PriorityQueue 实现最大堆，以便按照项目的利润从大到小进行排序。
Lambda 表达式：
- 在 Arrays.sort 和 PriorityQueue 的构造函数中使用 Lambda 表达式来定义排序规则。
循环与条件判断：
- 使用 for 循环来重复选择项目。
- 使用 while 循环来将所有可以启动的项目加入最大堆。
- 使用 if 语句来检查最大堆是否为空，以决定是否退出循环。
优先队列的操作：
- 使用 add 方法将项目添加到最大堆中。
- 使用 poll 方法从最大堆中取出并移除利润最大的项目。
变量操作：
- 使用累加操作来更新当前资本 w。
方法定义：
- 定义了一个 findMaximizedCapital 方法，它接受参数并返回一个整数值。
参数传递与返回值：
- 方法的参数包括整数 k、w，以及两个整数数组 profits 和 capital。
- 方法返回最终的资本值。
算法设计：
- 实现了一个贪心算法，通过选择当前可启动的利润最大的项目来最大化最终的资本。