# 703 Kth Largest Element in a Stream

設計一個KthLargest Class裡面有add function，每次add後要回傳當下的第k大數字。

class結構

class KthLargest {

    public KthLargest(int k, int[] nums) {

    }

    public int add(int val) {

    }
}

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

Idea create a pq always keep it's size as k ascending order, smaller in the front of pq

whenver get a number larger than pq.peek, pop the front out and push number to pq

Code

class KthLargest {
    PriorityQueue<Integer> pq;
    int k;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
            @Override
            public int compare(Integer p, Integer q){
                return p < q ? -1 : 1;
            }
        });

        for(int n : nums){
            if(pq.size() < k){
                pq.add(n);
            }else{
                if(pq.peek() < n){
                    pq.poll();
                    pq.add(n);
                }
            }
        }
    }

    public int add(int val) {
        if(pq.size() < k){
                pq.add(val);
        }else{
            if(pq.peek() < val){
                pq.poll();
                pq.add(val);
            }
        }

        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);
 */