贪心

方法一贪心

很直观的贪心问题，每一次抉择我们需要选取当前可以做的利润最大的项目。

参考代码

  1. class Solution {
  2.     public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
  3.         // 资本
  4.         PriorityQueue<Integer> capitalQueue = new PriorityQueue<>((o1,o2)->capital[o1] - capital[o2] );
  6.         // 利润
  7.         PriorityQueue<Integer> profitsQueue = new PriorityQueue<>((o1,o2)->profits[o2] - profits[o1]);
  10.         for(int i=0;i<capital.length;i++){
  11.             capitalQueue.add(i); 
  12.         }
  14.         for(int i=0;i<k;i++){
  15.             while(!capitalQueue.isEmpty() && capital[capitalQueue.peek()] <= w){
  16.                 profitsQueue.add(capitalQueue.poll());
  17.             }
  18.             if(profitsQueue.isEmpty()){
  19.                 break;
  20.             }
  21.             w += profits[profitsQueue.poll()];
  23.         }
  24.         return w;
  25.     } 
  26. }

复杂度分析

时间复杂度O((n+k)logn)
空间复杂度O(n)