一、问题中位数到底难在哪1.1 先把两个题面讲清楚LeetCode 295 数据流中位数Hard设计一个数据结构支持两个操作——addNum(int)往数据流里塞一个数findMedian()返回当前所有已塞数的中位数。要求两类操作都尽可能快。LeetCode 480 滑动窗口中位数Hard给一个数组nums和一个窗口大小k窗口每步右移一格返回每个窗口的中位数数组。两题都是 Hard但放在一起看骨架惊人地一致在一个动态变化的有序集合里反复查询中间那个数。区别只在于——295 只增不删485 边增边删窗口右移要踢掉最老的元素。1.2 为什么每次排序是死路最直观的想法维护一个有序数组来一个数就二分插入中位数直接取中间。方案addNumfindMedian插入排序有序数组O(n)要挪元素O(1)每次重新排序O(n log n)O(1)对顶堆O(log n)O(1)问题在于有序数组的插入是 O(n)因为物理上要把后面的元素一个个挪位置。而我们要的其实根本不是全部有序只是中间那个位置。为了找个中位数把整列排好序是拿牛刀杀鸡——而且这把牛刀还是 O(n)。这就是对顶堆出场的动机我们只需要一个分界线不需要整条有序序列。二、对顶堆的核心思想两个堆顶一条线2.1 把数劈成两半想象把当前所有数从小到大排好中位数正好坐在中间的分界线上。对顶堆做的事就是把这堆数劈成两半左半边lo大顶堆放较小的一半堆顶是这一半里最大的那个——也就是左半边界。右半边hi小顶堆放较大的一半堆顶是这一半里最小的那个——也就是右半边界。关键洞察中位数只可能出现在两个堆顶。如果总个数是奇数让lo比hi多一个那中位数就是lo的堆顶左半最大、也就是全体正中那个。如果总个数是偶数中位数就是两个堆顶的平均(-lo[0] hi[0]) / 2。注意 Python 的heapq只提供小顶堆所以大顶堆是靠存负数实现的——存-x弹出来再取负。这是本篇代码的统一约定。2.2 必须死守的不变量光有两个堆还不够必须维持一条平衡不变量len(lo) len(hi)或len(lo) len(hi) 1也就是lo的元素数要么和hi一样多偶数个要么比hi多一个奇数个。每插入一个数后都要检查并把多出来的那个堆顶弹给对方恢复平衡。这条不变量一旦破了中位数就对不准。下面这张图是插入一个数后的插入—平衡闭环三、LeetCode 295数据流中位数只增不删3.1 代码实现逻辑完全对应上面两图。addNum负责归堆 平衡findMedian只看堆顶。import heapq class MedianFinder: def __init__(self): self.small [] # 大顶堆(存负数), 放较小一半 self.large [] # 小顶堆, 放较大一半 def addNum(self, num: int) - None: if not self.small or num -self.small[0]: heapq.heappush(self.small, -num) else: heapq.heappush(self.large, num) # 平衡: small large 或 small large 1 if len(self.small) len(self.large) 1: heapq.heappush(self.large, -heapq.heappop(self.small)) elif len(self.large) len(self.small): heapq.heappush(self.small, -heapq.heappop(self.large)) def findMedian(self) - float: if len(self.small) len(self.large): # 奇数个 return float(-self.small[0]) return (-self.small[0] self.large[0]) / 2.0 # 偶数个3.2 本地真实运行输出我把它在本机 Python 3.12 跑了一遍依次塞1,2,3,4,5,6,7输出如下真实运行结果非杜撰add 1: 中位 1.0 add 2: 中位 1.5 add 3: 中位 2.0 add 4: 中位 2.5 add 5: 中位 3.0 add 6: 中位 3.5 add 7: 中位 4.0可以手动验证塞到 4 个数[1,2,3,4]时中位数是(23)/22.5塞到 7 个数时正中是第 4 个4.0。完全正确。3.3 复杂度addNum一次 push 至多一次跨堆搬运都是 O(log n)。findMedian只看两个堆顶O(1)。对比插入排序 O(n) 的插入数据流越大对顶堆的优势越夸张。四、LeetCode 480滑动窗口中位数边增边删4.1 为什么 480 比 295 难一档480 多了一个动作窗口右移时要把已经滑出窗口的最老元素删掉。问题来了——Python 的heapq是个死堆它只能弹堆顶没法在 O(log n) 时间里随机删除中间某个元素。那个被踢出去的元素可能正埋在某个堆的中间不是堆顶。这就是 480 的核心难点如何删除一个不在堆顶的元素4.2 解法惰性删除lazy deletion思路很妙既然现在删不掉那就先不删记账。维护一个字典dead记录这个数要被删但还埋在堆里。只有当这个数浮到堆顶、挡道了比如正好要被拿来当中位数或者要被搬运到另一个堆时才真正把它从堆里弹掉。同时维护两个堆的活跃元素计数lo_cnt / hi_cnt表示各自堆里真正还在窗口内的个数——因为堆的物理长度里混着待删元素不能直接拿物理长度做平衡。4.3 完整代码已对拍验证import heapq from collections import defaultdict def medianSlidingWindow(nums, k): lo [] # 大顶堆(存负数) 较小一半 hi [] # 小顶堆 较大一半 dead defaultdict(int) lo_cnt hi_cnt 0 # 两堆中仍在窗口内的活跃元素数 def clean(): # 把堆顶上挂着的待删元素真正弹掉 while lo and dead[-lo[0]]: dead[-lo[0]] - 1; heapq.heappop(lo) while hi and dead[hi[0]]: dead[hi[0]] - 1; heapq.heappop(hi) def balance(): nonlocal lo_cnt, hi_cnt total lo_cnt hi_cnt tgt (total 1) // 2 # lo 应有的活跃元素数 while lo_cnt tgt: clean() v -heapq.heappop(lo); lo_cnt - 1 heapq.heappush(hi, v); hi_cnt 1; clean() while lo_cnt tgt and hi_cnt 0: clean() v heapq.heappop(hi); hi_cnt - 1 heapq.heappush(lo, -v); lo_cnt 1; clean() def add(x): nonlocal lo_cnt, hi_cnt if not lo or x -lo[0]: heapq.heappush(lo, -x); lo_cnt 1 else: heapq.heappush(hi, x); hi_cnt 1 balance() def remove(x): nonlocal lo_cnt, hi_cnt clean() dead[x] 1 if x -lo[0]: # 判断 x 原本在哪个堆 lo_cnt - 1 else: hi_cnt - 1 clean(); balance() res [] for i, x in enumerate(nums): add(x) if i k - 1: clean() res.append(float(-lo[0]) if k % 2 1 else (-lo[0] hi[0]) / 2.0) remove(nums[i - k 1]) return res4.4 本地真实运行 对拍验证我用 LeetCode 官方示例、偶数窗口、以及与暴力法对拍三种方式验证真实运行结果示例1 [1,3,-1,-3,5,3,6,7] k3 输出: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0] 期望: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0] ✓ 完全一致 示例2 [1,2] k1 输出: [1.0, 2.0] 期望: [1.0, 2.0] ✓ 示例3 [1,4,2,3,5] k4 (偶数窗口) 输出: [2.5, 3.5] 期望: [2.5, 3.5] ✓ 随机 3000 元素多 k 值与暴力法(statistics.median)对拍: k1 一致: True k2 一致: True k3 一致: True k7 一致: True k8 一致: True k13 一致: True 性能: n300000, k500, 耗时约 657 ms对拍brute-force cross-check是这里的关键可信度来源随机造 3000 个数用statistics.median暴力算每个窗口再和双堆结果逐位比对6 个不同的 k 全部一致——说明惰性删除 活跃计数这套逻辑在边界重复元素、偶数窗口、删除元素正好是堆顶等上都没有偏差。4.5 三个最容易写错的坑写 480 时我自己踩了三个坑单独拎出来不能用堆的物理长度做平衡。dead里记账的元素还埋在堆里物理长度虚高。必须用活跃计数lo_cnt/hi_cnt否则平衡会越调越歪。移除后窗口大小变了target 要跟着变。remove之后窗口从 k 缩到 k-1balance的目标(total1)//2必须基于当前活跃总数不能写死成 k。取中位数前必须clean()。否则中位数可能取到一个本该被删、却刚好是堆顶的脏数据。五、横向对比对顶堆还能解什么对顶堆的本质是动态维护一个分界值举一反三它在一大批题目里都能套题目要维护的分界解法295 数据流中位数中间分位本文双堆480 滑动窗口中位数中间分位本文双堆 惰性删除295 的兄弟数据流第 K 大第 K 大单堆即可求两个有序流合并的中位数中间分位对顶堆思想的变形与前几篇 DSA 串一下8/25 写过单堆Top K215/347那是一个堆顶 淘汰本篇是两个堆互压 平衡复杂度模型从单维最值升级到了分位数维护。面试里 295 几乎是必考题480 是它的加难度版把删除这一环补上就算真正吃透了对顶堆。六、总结对顶堆 一个大顶堆压小顶堆堆顶连线就是中位数。只增场景295用标准平衡即可。边增边删场景480必须上惰性删除删不掉的元素先记账浮到堆顶再清并用活跃计数做平衡。复杂度每次插入/删除 O(log n)查询中位数 O(1)远胜排序法。工程可信度本文代码已在本地与暴力法对拍多 k 值一致不是看起来对。中位数问题的优雅之处在于它告诉你——很多时候我们不需要把全部信息排好序只需要维护好那一条分界线。这正是用 O(log n) 结构换 O(1) 查询的经典案例。参考资料LeetCode 295. Find Median from Data Stream题目与官方示例. https://leetcode.com/problems/find-median-from-data-stream/LeetCode 480. Sliding Window Median题目与官方示例. https://leetcode.com/problems/sliding-window-median/Python heapq 官方文档最小堆实现、存负数模拟最大堆. heapq — Heap queue algorithm — Python 3.14.7 documentationLeetCode 295 讨论区Two Heaps 标准解法. https://leetcode.com/problems/find-median-from-data-stream/discuss/LeetCode 480 讨论区Sliding Window Lazy Deletion 解法. https://leetcode.com/problems/sliding-window-median/discuss/