703. Kth Largest Element in a Stream - Easy

前往題目

想法

• 用priority queue

思路

1. 把初始array放進priority queue裡面
2. 每次加入的時候都先加入新的數字，然後再把pq刪減到剩下k項(因為這題只有add方法所以只要維持k個就好，因為k值固定所以更小的數字永遠不會用到)

Code

class KthLargest {
    private int k;
    private PriorityQueue<Integer> pq;
    private int[] nums;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.nums = nums;
        pq = new PriorityQueue<Integer>();
        
        // 加入pq
        for (int i = 0; i < nums.length; ++i) {
            pq.add(nums[i]);
        }

    }
    
    public int add(int val) {
        pq.add(val);
        // Remove elements until only k left
        while (pq.size() > k) {
            pq.poll();
        }
        return pq.peek();
    }
}