优先队列

堆的类型以及时间复杂度

image.png

返回数据流的第K大元素

https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

image.png

使用最小堆原理即可解决。就是取出前k个元素，使之成为最小堆，然后后面的元素每过来一个就和堆顶的数进行比较，如果小于堆顶的元素，即小于堆中所有元素，直接跳过即可。反之，加入并重置堆。最后返回该堆中的最小值即可。也就是第k大元素了。

class KthLargest {
    
    // 初始化一个优先级队列
    final PriorityQueue<Integer> pq;
    // 初始化k
    final int k;
    // 优先级队列的构造方法 传入k 和 int数组
    public KthLargest(int k, int[] nums) {
        this.k = k;
        // 初始化优先级队列 设定大小为k个
        pq = new PriorityQueue<>(k);
        // 遍历传入数组 构造优先级队列
        for (int n : nums) {
            add(n);
        }
    }
    
    // 添加新数据的方法 没添加一个新数据 则重新构造优先级队列 并返回第K大元素
    public int add(int val) {
        // 判断 如果优先级队列的大小还不够k 则继续添加 反之则返回队列顶级元素
        if (pq.size() < k) {
            pq.offer(val);
        // 如果传入元素大于优先级队列顶部元素 则移除优先级顶部元素 并重置优先级队列
        }else if (pq.peek() < val){
            pq.poll();
            pq.offer(val);
        }
        // 最后返回优先级队列顶部元素 即为第K大元素
        return pq.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

返回滑动窗口中的最大值

image.png

https://leetcode-cn.com/problems/sliding-window-maximum/submissions/

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 判空
        if (k == 0) {
            return nums;
        }
        // 初始化优先级队列 默认是小顶堆  我们使用表达式修改为大顶堆 也就是顶部是最大值
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> b - a);
        // 遍历数组前k位的值 并加入优先级队列
        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        // 初始化结果数组 起码有一个
        int[] res = new int[nums.length - k + 1];
        // 遍历结果数组
        for (int i = 0; i < res.length; i++) {
            // 把选出来的最大值放入结果数组
            res[i] = queue.peek();
            // 移除queue中重复元素
            queue.remove(nums[i]);
            // 判断是否越界 如果没有越界 则加入队列继续下一轮循环 来选出下一轮队列的最大值
            if (i + k < nums.length) {
                // 把每次移动一位的新元素加入优先级队列以便于下一次取
                queue.add(nums[i + k]);
            }
        }
        // 最后返回结果队列即可
        return res;
    }
}