[数据结构与算法]数据流中的第 K 大元素

703. 数据流中的第 K 大元素 - 力扣（LeetCode） (leetcode-cn.com)

考察知识点：优先队列 or 堆

直接思路是对nums排序，取第k大的元素。

由于是数据流，若来N个数，且使用快排，则时间复杂度为N·klogk。

实际上，只关心最大的K个数，每次新数据来时，都更新最大K个数即可。

保存K个最大数，每次返回第K大的数，很像堆的性质。

python的堆实现使用heapq库

python中使用优先队列 | 序语程言 (yangyanxing.com)

heapq --- 堆队列算法 — Python 3.10.1 文档

code:

import heapq
class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.k=k
        self.pq=nums
        heapq.heapify(self.pq)
        


    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        heapq.heappush(self.pq,val)
        while len(self.pq)>self.k:
            heapq.heappop(self.pq)
        return self.pq[0]