703 数据流中的第 K 大元素（小根堆）

曾经终败给现在 2022-09-04 01:58 159阅读 0赞

**1. 问题描述：**

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。  
请实现 KthLargest 类：  
KthLargest(int k, int\[\] nums) 使用整数 k 和整数流 nums 初始化对象。  
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

**示例：**

输入：  
\["KthLargest", "add", "add", "add", "add", "add"\]  
\[\[3, \[4, 5, 8, 2\]\], \[3\], \[5\], \[10\], \[9\], \[4\]\]  
输出：  
\[null, 4, 5, 5, 8, 8\]  
解释：  
KthLargest kthLargest = new KthLargest(3, \[4, 5, 8, 2\]);  
kthLargest.add(3); // return 4  
kthLargest.add(5); // return 5  
kthLargest.add(10); // return 5  
kthLargest.add(9); // return 8  
kthLargest.add(4); // return 8

**提示：**

1 <= k <= 10 ^ 4  
0 <= nums.length <= 10 ^ 4  
\-10 ^ 4 <= nums\[i\] <= 10 ^ 4  
\-10 ^ 4 <= val <= 10 ^ 4  
最多调用 add 方法 10 ^ 4 次  
题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream

**2. 思路分析：**

分析题目可以知道我们需要设计一个数据结构使得这个数据结构可以支持添加一个数的操作，删除最小值的操作，也即需要维护前k小的元素，可以使用**小根堆**来维护（一看到**维护前k小/大的数**那么想到的肯定是堆来维护），在初始化的时候我们可以将元素插入到堆中，当发现堆中元素大于k之后那么弹出堆顶元素即可，初始化和插入一个元素到堆中的过程都是一样的。因为使用的是python语言所以可以使用heapq模块对列表模拟堆的相关操作即可。

**3. 代码如下：**

from typing import List
    import heapq
    
    
    class KthLargest:
        nums = None
        k = 0
    
        def __init__(self, k: int, _nums: List[int]):
            self.k = k
            self.nums = list()
            for x in _nums:
                # 将元素插入到堆中
                heapq.heappush(self.nums, x)
                # 堆中元素大于了k之后那么弹出堆顶元素
                if len(self.nums) > k:
                    heapq.heappop(self.nums)
    
        def add(self, val: int) -> int:
            nums = self.nums
            heapq.heappush(nums, val)
            if len(nums) > self.k:
                heapq.heappop(nums)
            return nums[0]