设计一个找到数据流中第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。
切题
一、Clarification
没有特别需要注意的边界问题
二、Possible Solution
1、保存前k个最大值
通过排序找出第k大元素，时间复杂度 O(n*klogk) 其中O(klogk)为排序的时间复杂度，n为元素个数
2、借助小顶堆
Min Heap 中的元素个数为k，那么堆顶就为第k大元素。我们需要维护一个Min Heap，时间复杂度O(n*logk) 其中O(logk)为Min heap调整的时间复杂度。java中可以使用PriorityQueue，python可使用heapq库，也是优先队列算法。
python 实现
heapq--- 堆队列算法
# @author:leacoder
# @des: 借助小顶堆(heapq---堆队列算法也称为优先队列算法) , 数据流中的第K大元素
class KthLargest:
def __init__(self, k: int, nums: List[int]):
# heapq.nlargest(n, iterable, key=None) 返回一个列表，其中包含iterable定义的数据集中的n个最大元素。
self.k_heap = heapq.nlargest(k, nums)
# heapq.heapify(x) 将list x 转换成堆，原地，线性时间内
heapq.heapify(self.k_heap)
self.k = k
def add(self, val: int) -> int:
if len(self.k_heap) < self.k:
# 直接加入
heapq.heappush(self.k_heap,val)
else:
# 先加入再弹出最小，维护元素为k个
# heapq.heappushpop(heap, item) 将 item 放入堆中，然后弹出并返回 heap 的最小元素。
heapq.heappushpop(self.k_heap,val)
# 最小的元素总是在根结点：heap[0],由于维护的元素个数为k，那么就为第k大元素
return self.k_heap[0]
Java 实现
优先队列
/*
*@author:leacoder
*@des: 优先队列 数据流中的第K大元素
*/
class KthLargest {
final PriorityQueue<Integer> myqueue;
final int kMax;
public KthLargest(int k, int[] nums) {
myqueue = new PriorityQueue<>(k); //指定初始容量k的优先队列
kMax = k;
for(int n:nums){
add(n); //将数据加入到 优先队列中
}
}
public int add(int val) {
if(myqueue.size()<kMax){
myqueue.offer(val); //队列还未填满 直接入队
}
else if(myqueue.peek()<val){//队列顶 小于加入的val 说明第k大变为val，原来的变为k+1大
myqueue.poll();
myqueue.offer(val); //移除顶端 数据 加入新数据
}
return myqueue.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
GitHub链接：
https://github.com/lichangke/LeetCode
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习
