langShift堆（题单顺序）
热题 100 - 堆分组（按题单顺序）：215 / 347 / 295
本页包含题单「堆」分组的全部题目，顺序与 list.json 保持一致。
堆题统一“选型口诀”（点击展开）
- Top K 最大：用“小根堆”保留 k 个（堆顶是第 k 大）。
- Top K 最小：用“大根堆”保留 k 个（堆顶是第 k 小）。
- 中位数维护：左边大根堆 + 右边小根堆，保持尺寸差不超过 1。
- 存什么：需要比较时就把比较键（值/频次/距离）放到堆的 comparator 里，堆里通常存“元素本体或下标”。
215. 数组中的第 K 个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
最优解（小根堆保留 k 个最大：堆顶就是第 k 大）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：找第 k 大，不要求把整个数组排序完。
- 朴素做法：排序后取第 k 大，时间 (O(n\log n))。
- 关键推理：我们只关心“最大的 k 个数”，剩下的都可以丢：
- 用一个大小为 k 的 小根堆 保存“当前最大的 k 个数”。
- 堆顶是这 k 个数里最小的那个，也就是“第 k 大”的候选。
- 每来一个新数：
- 先放进堆
- 如果堆超过 k 个，就弹出最小的（也就是把不够大的淘汰）
- 处理完所有数后，堆里刚好是最大的 k 个，堆顶就是第 k 大。
类似题目（TopK 模板：小根堆保留 k 个最好）
for x in nums:heap.push(x)if heap.size > k: heap.pop() // 弹最差return heap.peek()
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
最优解（哈希计数 + 小根堆按频次保留 k 个）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 问题拆解：
- 先统计每个数出现次数（哈希表）
- 再从这些“(数,频次)”里选出频次最高的 k 个（TopK）
- 为什么用小根堆？：和 215 一样，“保留最好的 k 个”最稳的做法就是小根堆：
- 堆顶是当前 k 个里频次最小的（最容易被淘汰）。
- 新元素频次更大时，会把堆顶挤掉。
- 复杂度：统计 (O(n))，堆操作 (O(u\log k))（u 是不同元素个数），整体很高效。
类似题目（先计数再 TopK）
freq = count()heap keep k by key=freq
295. 数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
-
MedianFinder()初始化MedianFinder对象。 -
void addNum(int num)将数据流中的整数num添加到数据结构中。 -
double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
提示:
-105 <= num <= 105- 在调用
findMedian之前，数据结构中至少有一个元素 - 最多
5 * 104次调用addNum和findMedian
最优解（双堆：大根堆存左半，小根堆存右半）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 中位数的本质：把数据分成左右两半：
- 左半都 ≤ 右半
- 两边数量尽量相等（最多差 1）
- 关键推理：用两个堆维护这两个半区：
left（大根堆）：存较小的一半，堆顶是左半最大值right（小根堆）：存较大的一半，堆顶是右半最小值
- 插入一个数怎么做？
- 先把它放进合适的一边（
<=left 顶就进 left，否则进 right）。 - 然后做“平衡操作”：让 left 的大小永远 >= right，且最多多 1。
- 先把它放进合适的一边（
- 中位数怎么取？
- 总数奇数：left 比 right 多 1，中位数就是
left.peek() - 总数偶数：两边一样大，中位数是
(left.peek()+right.peek())/2
- 总数奇数：left 比 right 多 1，中位数就是
类似题目（动态维护中位数：双堆平衡）
add:push to left/rightrebalance sizesmedian:if left bigger: left.topelse avg(left.top, right.top)