Leetcode刷题100天—502. IPO( 优先队列)—day32

た入场券 2022-09-12 13:49 187阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210908202343610][]

#### [502. IPO][] ####

难度困难127收藏分享切换为英文接收动态反馈

假设 力扣（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 <= 105`
 *  `0 <= w <= 109`
 *  `n == profits.length`
 *  `n == capital.length`
 *  `1 <= n <= 105`
 *  `0 <= profits[i] <= 104`
 *  `0 <= capital[i] <= 109`

package 优先队列;
    
    import java.util.Arrays;
    import java.util.PriorityQueue;
    
    /* * https://leetcode-cn.com/problems/ipo/ * 解题思路 * 1. 按所需要的资本排序 * 2. 在小于等于总资本的项目启动资本中选择最大的利润项目 * 3. 更新总资本w * 4.重复2和3的操作,直到选择k次 * 解题方法 * 1.小于等于总资本的项目压入堆中 * 2.利用大根堆，每次取出最大利润，更新手中资本 * 3. 重复1 2操作 * 4. 如果当前的堆为空，则此时我们应当直接返回。 */
    public class _502_IPO { 
        public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { 
    // 定义一个数组指针
        	int node=0;
    // 将项目利润和资本合并成二维数组
    		int[][] res=new int [profits.length][2];
    		for(int i=0;i<profits.length;i++) { 
    			res[i][0]=profits[i];
    			res[i][1]=capital[i];
    		}
    // 对二维数组进行排序，排序的依据是最小资本capital
    		Arrays.sort(res,(a,b)->a[1]-b[1]);
    // 定义优先队列,从大到小排序输入进来的利润
    		PriorityQueue<Integer> queue=new PriorityQueue<>((x,y)->y-x);//大顶堆
    		
    // 如果到达指定的k个项目就停止
    		while(k-->0) { 
    // 通过循环将符合条件的资本入队
    			while(node<profits.length&& res[node][1]<=w) { 
    				queue.add(res[node][0]);
                    node++;
    			}
    // 如果队列为空，就出队利润加入到总资产里
    			if (!queue.isEmpty()) { 
    				w=w+queue.poll();
    			}else { 
    // 如果队列为空说明没有符合资本的项目了
    				break;
    			}
    		}
    		return w;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210908202343610]: /images/20220828/db9cd2e3b27a460e946e59e8426b18e8.png
[502. IPO]: https://leetcode-cn.com/problems/ipo/