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

时间:2024-09-21 23:36:20

设计一个找到数据流中第 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();
}
}