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

佚名 5年前 (2019-06-02) 算法 955人围观抢沙发百度已收录

设计一个找到数据流中第 K 大元素的类（class）。注意是排序后的第 K 大元素，不是第 K 个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组 nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第 K 大的元素。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

示例:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

说明:
你可以假设 nums 的长度≥ k-1 且 k ≥ 1。

解答：维护一个大根堆和一个小根堆，小根堆存放最大的K-1个元素，大根堆存放剩余的元素。当小根堆放入第K个元素后，取出小根堆堆顶元素放入大根堆。因此小根堆内元素个数永远是k-1，大根堆的堆顶元素就是我们要的第K大元素

class KthLargest {

    private PriorityQueue<Integer> bigHeap;
    private PriorityQueue<Integer> smaHeap;
    public KthLargest(int k, int[] nums) {
        bigHeap = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));
        smaHeap = new PriorityQueue<>((o1,o2)->o1.compareTo(o2));
        for(int i=0;i<k-1;i++){
            smaHeap.offer(nums[i]);
        }
        for(int i=k-1;i<nums.length;i++){
            smaHeap.offer(nums[i]);
            bigHeap.offer(smaHeap.poll());
        }
    }
    
    public int add(int val) {
        smaHeap.offer(val);
        bigHeap.offer(smaHeap.poll());
        return bigHeap.peek();
    }
}