502. IPO（贪心算法+优先队列/堆）-Toy模板网

这篇具有很好参考价值的文章主要介绍了502. IPO（贪心算法+优先队列/堆）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

整体思想：在满足可用资金的情况下，选择其中利润最大的业务，直到选到k个业务为止，注意k可能比n大。

每次选择完一个业务，可用资金都会变动，这是可选择的业务也会变化，因此每次将可选择的业务放在一个优先队列（大顶堆）中，堆顶元素就是目标业务。

优先队列（堆）的实现方式：优先队列，自定义比较器。

另外注意，将业务根据所需资金capacity进行升序排列，达到一种剪枝的目的。

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            list.add(new int[] {capital[i], profits[i]});
        }
        Collections.sort(list, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        int i = 0;
        while (k-- > 0) {
            while (i < n && list.get(i)[0] <= w) q.add(list.get(i++)[1]);
            if (q.isEmpty()) break;
            w += q.poll();
        }
        return w;
    }
}

拓展：

优先队列

在Java中，优先队列（PriorityQueue）是一种特殊的队列，它可以确保队列中元素的顺序是按照它们的优先级进行排列的数据结构。在优先队列中，具有较高优先级的元素会先被处理，而具有较低优先级的元素会被放置在队列的尾部。

优先队列可以用于许多应用，比如任务调度、事件模拟等。在Java中，优先队列通常是基于堆（Heap）实现的，这意味着它可以高效地支持插入和删除具有最高（或最低）优先级的元素。
```
import java.util.PriorityQueue;  
  
public class Main {  
    public static void main(String[] args) {  
        // 创建一个优先队列  
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();  
  
        // 向优先队列中添加元素  
        priorityQueue.add(3);  
        priorityQueue.add(1);  
        priorityQueue.add(2);  
  
        // 输出队列中的元素（按照优先级顺序）  
        while (!priorityQueue.isEmpty()) {  
            System.out.println(priorityQueue.poll());  
        }  
    }  
}  
```
需要注意的是，当元素被添加到优先队列中时，它们会根据其自然顺序或者根据提供的比较器进行排序。默认情况下，优先队列会按照元素的自然顺序进行排序，但也可以通过提供自定义的比较器来改变排序规则。
比较器

在Java中，Collections.sort 方法用于对集合进行排序。它可以接受一个比较器（Comparator）作为第二个参数，以便根据指定的比较规则对集合中的元素进行排序。

比较器是一个接口，它定义了用于比较两个对象顺序的规则。在Collections.sort中，当传入比较器时，它将根据比较器所定义的规则对集合中的元素进行排序。

具体来说，比较器的定义如下：
```
public interface Comparator<T> {
    int compare(T o1, T o2);
}
```
这个接口中的 compare 方法接受两个参数 o1 和 o2，分别代表要比较的两个对象。在这个方法中，需要定义比较规则，返回一个负整数、零或者正整数，分别表示第一个参数小于、等于或大于第二个参数。

在实际使用中，可以通过创建实现了Comparator接口的类，或者使用Lambda表达式来定义比较器。比如：
```
List<Integer> numbers = Arrays.asList(3, 1, 2);
Collections.sort(numbers, (a, b) -> a - b);
```
在这个例子中，(a, b) -> a - b 就是一个比较器，它定义了对整数列表进行升序排序的规则。具体来说，它告诉Collections.sort方法按照元素的大小进行排序。

总之，比较器允许我们根据特定的规则对集合中的元素进行排序，从而满足不同的排序需求。文章来源地址https://www.toymoban.com/news/detail-822311.html