教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文围绕「算法通关手册」题解库中的 LeetCode 0703. 数据流中的第 K 大元素 展开数据流是持续追加、无法一次性加载全部元素的数据形态本题要求设计一个KthLargest类在每次向流中插入新值后都能快速回答当前第 k 大的元素是多少。读完本文你将掌握经典的「维护大小为 k 的最小堆小顶堆」解法理解 Top-K 问题为什么选择堆而不是全量排序并能结合仓库中优先队列的源码实现吃透堆的底层原理为后续处理数据流中位数前 K 个高频元素等进阶题打下基础。一、题目与核心要求LeetCode 第 0703 题「数据流中的第 K 大元素」在仓库中归入 优先队列堆题目分类 下的优先队列题目列表标签为树、设计、二叉搜索树、二叉树、数据流、堆优先队列难度为简单是 Top-K 类问题的入门代表题。1.1 设计目标需要设计一个KthLargest类用于找到数据流中第 $k$ 大的元素实现两个方法KthLargest(int k, int[] nums)使用整数 $k$ 和整数流 $nums$ 初始化对象int add(int val)将 $val$ 插入数据流 $nums$ 后返回当前数据流中第 $k$ 大的元素。第 k 大的含义将所有已插入的元素从大到小排列后位于第 $k$ 位的元素。例如数据流为[4, 5, 8, 2]时从大到小为[8, 5, 4, 2]第 3 大是4。1.2 数据约束题目给出的数据范围决定了算法的选型约束项取值范围$k$$1 \le k \le 10^4$初始化数组长度 $nums.length$$0 \le nums.length \le 10^4$元素取值 $nums[i]$$-10^4 \le nums[i] \le 10^4$新插入值 $val$$-10^4 \le val \le 10^4$add方法最多调用次数$10^4$ 次查询前提题目数据保证查找第 k 大元素时数据流中至少有 $k$ 个元素注意两个细节其一nums.length可以为 0即允许用空数据流初始化其二数据是流式的add最多被调用 $10^4$ 次这意味着每次插入后都重新全量排序$O(n \log n)$在 $n$ 接近 $2 \times 10^4$ 时会累积成超大规模计算因此必须寻找增量的高效维护方式。1.3 示例演示输入 [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逐次推演初始k 3数据流[4, 5, 8, 2]中第 3 大为4插入3后数据流[4, 5, 8, 2, 3]从大到小为[8, 5, 4, 3, 2]第 3 大仍是4插入5后为[8, 5, 5, 4, 3, 2]第 3 大为5插入10后为[10, 8, 5, 5, 4, 3, 2]第 3 大仍为5插入9后为[10, 9, 8, 5, ...]第 3 大为8插入4后第 3 大仍为8。二、解题思路为什么用堆2.1 朴素思路的代价最容易想到的做法是每次add时把元素追加进列表然后排序取倒数第 $k$ 个。但每次插入都触发一次全量排序单次开销 $O(n \log n)$$10^4$ 次插入累积后代价极高在本题数据规模下并不理想。另一种思路是维护一个有序结构插入时二分定位后插入虽然查找第 $k$ 大是 $O(1)$但有序数组的插入本身是 $O(n)$需要搬移元素。2.2 Top-K 问题的标准范式固定大小的堆本题只关心第 k 大的元素等价于关心「当前数据流中最大的 k 个元素里最小的那个」。因此可以只保留 $k$ 个候选冠军其余更小的元素对答案没有任何影响可以直接丢弃。这引出了经典结论维护一个大小为 $k$ 的小顶堆堆中始终存放当前数据流中最大的 $k$ 个元素那么堆顶堆中的最小值就是整个数据流中的第 $k$ 大元素。这里需要澄清一个易混淆点原题解文档写作建立大小为 $k$ 的大顶堆但从实现与语义上看实际上维护的是一个大小为 $k$ 的小顶堆min_heap堆顶是最小的元素正因为堆顶是前 k 大中最小的那一个它才恰好等于第 $k$ 大。之所以用最小堆存最大的 k 个而非最大堆是因为每次只淘汰一个最不值得保留的元素比当前堆顶还小的元素直接无关紧要插入与淘汰都能以 $O(\log k)$ 完成。三、思路 1堆小顶堆维护 Top-K3.1 算法步骤建立大小为 $k$ 的小顶堆堆中元素个数保证不超过 $k$ 个每次add操作时将新元素压入堆中如果堆中元素个数超出了 $k$ 个则将堆中最小元素堆顶移除使堆始终只保留最大的 $k$ 个元素此时堆中最小元素堆顶就是整个数据流中的第 $k$ 大元素直接返回。该过程有两个天然的等价表述初始化时把nums中的每个元素都走一遍插入 超限淘汰流程即可在构造阶段建立好初始堆add只是对单个元素重复同样的流程。3.2 完整代码import heapq from typing import List class KthLargest: def __init__(self, k: int, nums: List[int]): # 小顶堆始终存放当前数据流中最大的 k 个元素 self.min_heap [] # 记录 k 值供 add 方法判断堆是否超限 self.k k # 初始化逐个元素执行“插入 超限淘汰” for num in nums: heapq.heappush(self.min_heap, num) if len(self.min_heap) k: # 堆顶是堆中最小元素弹出后堆恰好保留前 k 大 heapq.heappop(self.min_heap) def add(self, val: int) - int: # 新元素先入堆 heapq.heappush(self.min_heap, val) # 若堆大小超过 k弹出堆顶最小值维持“只保留前 k 大”的不变量 if len(self.min_heap) self.k: heapq.heappop(self.min_heap) # 堆顶即当前数据流的第 k 大元素 return self.min_heap[0]说明原题解中使用List[int]注解需要从typing导入若在 LeetCode 环境中该注解通常已由平台预处理提供本地运行时请自行补充导入。heapq是 Python 标准库中基于数组实现的堆队列算法模块其内部操作全部为 $O(\log n)$。3.3 代码逐行剖析self.min_heap []堆在 Python 中用普通列表承载heapq模块约定heap[0]即堆顶最小元素。初始化循环对nums中每个元素执行heappush一旦堆超过k个元素立即heappop弹出堆顶。最终堆内恰好是nums中最大的 $k$ 个元素。nums为空时循环体不执行堆保持为空此时由于题目保证查询第 k 大时至少有 k 个元素后续add会先补齐元素。add方法新值先无条件入堆即使它很小也要先入堆再淘汰因为无法预知它是否比堆内某些元素大随后检查堆是否超限并弹出堆顶。这一先入后淘汰的顺序保证了任何时候堆大小 $\le k$。return self.min_heap[0]小顶堆堆顶是堆内最小值也就是前 k 大中的最小者即第 $k$ 大元素。3.4 复杂度分析时间复杂度初始化$O(n \times \log k)$其中 $n$ 为初始化时nums的元素个数单次插入$O(\log k)$add方法每次至多执行一次heappush与一次heappop空间复杂度$O(k)$堆中最多同时存在 $k$ 个元素。相比每次全量排序的 $O(n \log n)$堆方案把单次插入降到对数级且空间只随 $k$ 增长、与数据流总量无关这正是它适合数据流场景的根本原因。四、从仓库源码看堆的实现原理为了深入理解heapq背后发生了什么可以对照仓库中优先队列与堆的源码实现。4.1 手写二叉堆入队与出队的本质仓库 queue_priority_queue.py 提供了一个完整的Heapq手写实现包含四个核心操作heapAdjust(nums, index, end)堆调整从指定根节点出发自上而下比较并交换使以该节点为根的子树重新满足堆性质该实现调整的是大顶堆heapify(nums)建堆从最后一个非叶节点(size - 2) // 2开始依次向前执行堆调整heappush(nums, value)入队先把新元素追加到数组末尾再从下往上寻找插入位置自底向上的上浮调整heappop(nums)出队将堆顶与末尾元素交换后弹出末尾再对新堆顶执行一次堆调整自上而下的下沉调整。其中heappush的关键逻辑是新元素value从末尾下标出发与其父节点(i - 1) // 2反复比较父节点更大则把父节点下移直到找到合适位置插入。这与heapq的内部实现思路一致只是heapq维护的是小顶堆比较方向相反。4.2 堆的数组存储与下标规律堆在逻辑上是一棵完全二叉树但在编程中用数组顺序存储仓库文档 01_09_array_heap_sort.md 总结了关键下标规律节点下标为 $i$ 时左孩子下标为 $2 \times i 1$右孩子下标为 $2 \times i 2$节点下标为 $i$ 时父节点下标为 $\lfloor (i - 1) / 2 \rfloor$。这套下标换算正是heapAdjust、heappush等操作定位父子节点的依据也是heapq模块能用普通列表模拟堆结构的前提。4.3 大顶堆的手写封装示例仓库 array_maxheap.py 提供了MaxHeap类的完整封装包含peek()$O(1)$ 返回堆顶、push()追加到末尾后__shift_up上浮调整、pop()交换堆顶与末尾后弹出并__shift_down下沉调整。这套上浮/下沉二件套与优先队列文档 03_04_priority_queue.md 中介绍的一致。若面试中被要求不使用标准库完全可以参照该实现手写一个小顶堆版KthLargest。4.4 关于 heapq 的注意事项heapq默认是小顶堆heappop弹出的是堆中的最小值这恰好契合本题保留前 k 大、淘汰最小的需求无需任何改造如果题目要求的是第 k 小元素则可以维护大小为 $k$ 的大顶堆或利用heapq存负数的技巧如仓库文档 03_04_priority_queue.md 所述将优先级取负数存入堆中需要保证相同优先级元素按入队顺序时可额外存储一个自增索引这也是优先队列进阶实现中的常见手法。五、常见误区与边界情况5.1 大顶堆还是小顶堆原题解中建立大小为 $k$ 的大顶堆的说法容易引起误解。从语义与代码双重验证可知本题应当维护大小为 $k$ 的小顶堆堆内是最大的 k 个元素堆顶是其中最小者即第 $k$ 大元素。若真的使用大顶堆堆顶会变成最大的元素与第 k 大不符。阅读仓库题解时建议以代码实现为准理解题意。5.2 初始化时 nums 为空由于nums.length可以为 0__init__中循环体不会执行堆为空。此时若恰好k 0而nums为空只要题目保证后续查询时数据流中已有至少 $k$ 个元素本题有此保证第一次add后堆就能满足查询条件无需单独处理。5.3 重复元素元素值允许重复示例中输入包含两个5、两个8的输出。堆按值比较重复元素作为独立节点参与插入与淘汰不额外去重因此答案会正确地把重复值计入排名。5.4 负数值取值范围包含负数$-10^4 \le nums[i], val \le 10^4$。heapq对负数一视同仁按数值大小正常比较无需特殊处理。六、举一反三相关题目与延伸本题是优先队列堆分类下的经典入门题仓库 00_06_categories_list.md 的「优先队列题目」列表中还收录了同类型题目按难度递进推荐练习0215. 数组中的第 K 个最大元素静态数组版的 Top-K 问题难度中等。仓库题解给出了堆排序、快速选择、借标准库排序、优先队列四种思路其中优先队列思路与本题目的一致可对比理解静态数组与数据流场景下堆解法的异同LCR 059. 数据流中的第 K 大元素与本题完全同源同一算法题的 LCR 变体题解采用同样的heapq小顶堆方案可作为快速复习素材数据流的中位数295进阶版双堆问题用大顶堆 小顶堆协作维护中位数进一步体会堆在数据流问题中的威力前 K 个高频元素347、根据字符出现频率排序451哈希表统计 堆的经典组合。总结LeetCode 0703「数据流中的第 K 大元素」是 Top-K 问题的入门基石。核心结论只有一条用大小为 $k$ 的小顶堆维护当前最大的 k 个元素堆顶即答案。初始化 $O(n \log k)$、单次插入 $O(\log k)$、空间 $O(k)$ 的复杂度特性使其成为处理流式数据的标准方案。配合仓库中 queue_priority_queue.py 与 array_maxheap.py 的手写堆实现、03_04_priority_queue.md 与 01_09_array_heap_sort.md 的理论讲解建议读者在掌握标准库heapq解法后再动手手写一遍堆的上浮/下沉操作即可彻底吃透本题并平滑过渡到更复杂的堆应用题。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 703「数据流中的第 K 大元素」基于最小堆的流式 Top-K 求解方案Kth Largest Integer in a StreamLeetCode 703「数据流中的第 K 大元素」基于最小堆的流式 Top K 求解方案Kth Largest Integer in a Stream示例工程教程Hello 算法Top-k 问题深度剖析——如何用最小堆从无序数组中高效找出最大的 k 个元素Hello 算法Top k 问题深度剖析——如何用最小堆从无序数组中高效找出最大的 k 个元素 Top k 问题Top k Problem是堆heap教程文档示例工程教育深度解析如何掌握SMU Debug Tool释放AMD Ryzen处理器的隐藏性能深度解析如何掌握SMU Debug Tool释放AMD Ryzen处理器的隐藏性能 想要完全掌控AMD Ryzen处理器的性能潜力吗SMU Debug To教程文档示例工程教育上一篇PeachPy内联汇编功能在Python中直接调用汇编代码的终极指南下一篇B站缓存视频永久保存方案m4s无损转MP4完整教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考