LeetCode 703. 数据流中的第 K 大元素

题目链接：

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

【分析】维护一个有k个元素的最小堆，再来一个元素后，如果这个元素比堆顶大，就把堆顶弹出然后把这个元素压入堆中。

class KthLargest {

    PriorityQueue queue = new PriorityQueue<>();
    public KthLargest(int k, int[] nums) {
        int i, n = nums.length;
        for(i = 0; i < k; i++){
            queue.offer(Integer.MIN_VALUE);
        }
        for(i = 0; i < n; i++){
            add(nums[i]);
        }
    }

    public int add(int val) {
        if(queue.isEmpty()) queue.offer(val);
        else{
            if(val > queue.peek()){
                queue.poll();
                queue.offer(val);
            }
        }
        return queue.peek();
    }
}

【优化】其实可以不用一开始就加入k个最小值然后维护，可以在加入的时候，如果堆的大小大于k了就把堆顶弹出即可。

class KthLargest {

    PriorityQueue queue = new PriorityQueue<>();
    int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for(Integer it: nums){
            queue.offer(it);
        }
    }

    public int add(int val) {
        queue.offer(val);
        while(queue.size() > k){
            queue.poll();
        }
        return queue.peek();
    }
}