优先队列排序（JAVA）

执行K次最大分数_力扣每日一题

思路：执行k次，每次取出数组中的最大值，结果需要和最大值/3向上取整求和。最后返回最大值。注意：1 <= nums.length, k <= 10^5,时间复杂度控制在O（n）。

如果每次排序做，然后遍历数组，会超时。所以使用优先队列（这里是大根堆），每次取出队头，取出之后再插入它的三分之一向上取整。

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
class Solution {
    public long maxKelements(int[] nums, int k) {
        PriorityQueuepriorityQueue=new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int i=0;i< nums.length;i++){
            priorityQueue.offer(nums[i]);
        }
        long ans=0;
        while(k>0)
        {
            int num=priorityQueue.poll();
            ans+=num;
            num=(int)Math.ceil((double)num/3);
            priorityQueue.offer(num);
            k--;
        }
        return ans;
    }
}

关于优先队列的一些小结：

方法：

• • boolean	add(E e) 将指定的元素插入到此优先级队列中。
    void	clear() 从此优先级队列中删除所有元素。
    ComparatorE>	comparator() 返回用于为了在这个队列中的元素，或比较null如果此队列根据所述排序natural ordering的元素。
    boolean	contains(Object o) 如果此队列包含指定的元素，则返回 true 。
    Iterator<E>	iterator() 返回此队列中的元素的迭代器。
    boolean	offer(E e) 将指定的元素插入到此优先级队列中。
    E	peek() 检索但不删除此队列的头，如果此队列为空，则返回 null 。
    E	poll() 检索并删除此队列的头，如果此队列为空，则返回 null 。
    boolean	remove(Object o) 从该队列中删除指定元素的单个实例（如果存在）。
    int	size() 返回此集合中的元素数。
    Spliterator<E>	spliterator() 在此队列中的元素上创建late-binding和失败快速 Spliterator 。
    Object[]	toArray() 返回一个包含此队列中所有元素的数组。
    T[]	toArray(T[] a) 返回一个包含此队列中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。

优先队列默认小根（顶）堆。元素单调递增。

如果要自定义排序，需要重写Compare方法。

大根堆：

PriorityQueuepriorityQueue=new PriorityQueue<>(new Comparator() {
    @Override
    public int compare(Integer o1, Integer o2) {
    return o2-o1;
    }
});