LeetCode 数据流中第K大元素题解

LeetCode 数据流中第K大元素题解题目描述设计一个数据流找到数据流中第 k 大的元素。示例输入k 3,arr [4,6,5]输出5解题思路方法堆思路使用最小堆维护前 k 大的元素。遍历数据流将每个元素加入堆中。如果堆的大小超过 k则弹出堆顶元素。最后堆顶元素就是第 k 大的元素。复杂度分析时间复杂度O(n log k)空间复杂度O(k)代码实现import heapq class KthLargest: def __init__(self, k, nums): self.k k self.heap [] for num in nums: heapq.heappush(self.heap, num) if len(self.heap) k: heapq.heappop(self.heap) def add(self, val): heapq.heappush(self.heap, val) if len(self.heap) self.k: heapq.heappop(self.heap) return self.heap[0] # 测试 def test_kth_largest(): k 3 nums [4, 6, 5] kth KthLargest(k, nums) print(kth.add(7)) # 输出5 print(kth.add(8)) # 输出6 if __name__ __main__: test_kth_largest()总结数据流中第K大元素是堆的典型应用通过维护一个大小为 k 的堆来找出第 k 大的元素。