# 703. Kth Largest Element in a Stream 数据流中的第 K 大元素

@TOC

## # 题目描述

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your `KthLargest` class will have a constructor which accepts an integer `k` and an integer array `nums`, which contains initial elements from the stream. For each call to the method `KthLargest.add`, return the element representing the kth largest element in the stream.

Example:

``````int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
``````

Note:

You may assume that nums' length ≥ k-1 and k ≥ 1.

## # 解题方法

### # 小根堆

Python的堆是小根堆，不需要对其进行转换，我们想一想，如果一个堆的大小是k的话，那么最小的数字就在其最前面（即为第k大的数字），只要维护当新来的数字和最前面的这个数字比较即可。

``````class KthLargest(object):

def __init__(self, k, nums):
"""
:type k: int
:type nums: List[int]
"""
self.pool = nums
self.size = len(self.pool)
self.k = k
heapq.heapify(self.pool)
while self.size > k:
heapq.heappop(self.pool)
self.size -= 1

"""
:type val: int
:rtype: int
"""
if self.size < self.k:
heapq.heappush(self.pool, val)
self.size += 1
elif val > self.pool[0]:
heapq.heapreplace(self.pool, val)
return self.pool[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)