0703. Kth Largest Element in a Stream #

题目 #

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
- KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
- int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

思路 #

堆 #

代码 #

堆 #

class KthLargest {
    private int k;
    private Queue<Integer> pq;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.pq = new PriorityQueue<>();
        for (int num: nums) {
            if (this.pq.size() == k && this.pq.peek() < num) this.pq.poll();
            if (this.pq.size() < k) this.pq.offer(num);
        }
    }
    
    public int add(int val) {
        if (this.pq.size() == this.k && this.pq.peek() < val) this.pq.poll();
        if (this.pq.size() < this.k) this.pq.offer(val);
        return this.pq.toArray(new Integer[this.pq.size()])[0];
    }
}

致谢 #

负雪明烛