703. Kth Largest Element in a St

通过这道题复习一下python heap操作：
import heapq
python里面heapq用list实现的是最小堆，也就是每次pop（）出来的是最小的数字。有以下method：

q = []
heappush(q, item)
heappop(q) # 如果只想看一下最小的不取出来，则用q[0]即可
heappushpop(q, item) # 先push再pop
heapify(q) # Transform list x into a heap, in-place, in linear time.
heapreplace(q, item) #先pop再push
nlargest(n, q) # return 前n个最大的数作为list

comparator 模版

Screen Shot 2018-12-05 at 12.13.04 PM.png

回到这道题，这道题可以建立一个大小为k的堆，存放最大的k个数，然后新加进来的数再pop掉最小的。
python代码如下：

import heapq
class KthLargest:

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

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        else:
            heapq.heappushpop(self.heap, val)
            
        return self.heap[0]


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