设计一个找到数据流中第 K 大元素的类（class）。注意是排序后的第 K 大元素，不是第 K 个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组 nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第 K 大的元素。
示例:
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();
}
}