通過這道題復(fù)習(xí)一下python heap操作：
import heapq
python里面heapq用list實現(xiàn)的是最小堆，也就是每次pop（）出來的是最小的數(shù)字。有以下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個最大的數(shù)作為list

comparator 模版

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

回到這道題，這道題可以建立一個大小為k的堆，存放最大的k個數(shù)，然后新加進來的數(shù)再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)