企业官网建设流程全解析

你要是最近在准备算法面试，数据流中位数和滑动窗口中位数这对双子星，应该已经被各种高频题清单反复点名了。名义上是两个题，本质其实是同一个模型：在一个动态变化的集合里，维护一个能随时回答“当前中位数是多少”的结构。而解决这个模型最经典、也最常被面试官期待听到的工具，就是对顶堆。

这篇文章我会用聊天的口吻，把对顶堆的原理、数据流中位数的实现、滑动窗口中位数的实现，以及我在面试和带人准备面试时踩过的一些坑，全部串起来讲一遍。不管你是刚开始刷题的新手，还是已经刷了一段时间但遇到堆就发怵的选手，按这条线走一遍，应该都能对这类题建立起自己的判断框架。

1. 为什么数据流中位数和滑动窗口中位数，都绕不开对顶堆

1.1 中位数不是“排序后取中间”这么简单

中位数的定义大家小学就学过：把一组数按从小到大排好，取中间那个。如果是偶数个数，取中间两个的平均值。但这里藏着一个问题：定义是静态的，而数据流和滑动窗口里的集合是动态的。

数据流意味着每来一个数，集合规模就变大一点；滑动窗口意味着每移动一格，走一个旧数、进一个新数。如果每次求中位数都把整个集合重新排一遍，复杂度就是 (O(n \log n)) 甚至更高。面试官真正想看的，不是你能不能写出排序，而是你能不能发现中位数本质上是一个“位置维护”问题：我只关心中间那个位置上的数，没必要把整个序列都排好。

这就像你维护一个班级的成绩单，如果只想知道谁排中间，不需要每次都把全班重新按名次贴一遍墙，只要把左右两边的人数控制住就行了。对顶堆就是干这件事的结构。

1.2 对顶堆：一个管小区，一个管大区

对顶堆的英文叫 two heaps，中文翻译很形象。它由两个堆组成：

• 一个最大堆，负责装数据中“比较小的一半”，我们叫它左堆。
• 一个最小堆，负责装数据中“比较大的一半”，我们叫它右堆。
• 左堆的堆顶是左半边最大的元素，右堆的堆顶是右半边最小的元素。

只要保证左堆里所有元素都小于等于右堆里所有元素，并且两个堆的大小相差不超过 1，那么中位数就能直接用两个堆顶算出来：

• 如果总数是奇数，左堆比右堆多一个，左堆堆顶就是中位数。
• 如果总数是偶数，两个堆一样大，中位数是左堆堆顶和右堆堆顶的平均值。

为什么能保证左堆所有元素都小于右堆？靠的不是每次插入后重新整理全堆，而是靠插入时的“乾坤大挪移”：先往某一边塞，再取堆顶扔到另一边。堆本身只保证堆顶有序，但经过这种转移后，左右两半的相对顺序就会维持住。

1.3 插入后的平衡口诀：先塞左边，再丢右边，不够再捞

很多初学者第一次写对顶堆时，会把平衡逻辑搞得很复杂，又是 if 又是 while。其实核心就三句话：

1. 新数先塞进左堆（最大堆）。
2. 从左堆弹出堆顶，丢到右堆（最小堆）。
3. 如果此时左堆比右堆少，再从右堆弹出堆顶，捞回左堆。

第一步先把新数放到左堆，让它和左堆里的元素比较一轮，左堆的堆顶自然就是整个左半边最大元素。第二步把左堆堆顶丢到右堆，实际上是在做“分流”：如果新数很大，它会通过左堆堆顶的位置被送进右堆；如果新数很小，被丢过去的是原来的左堆堆顶，新数会留在左堆更靠里的位置。第三步调整大小，保证左堆永远不比右堆少。

这个流程每步都是 (O(\log n))，但逻辑非常稳，面试时不容易写乱。

2. 数据流中位数：双堆直落，代码一次写对

2.1 准备两个堆之前，先想清楚大小约定

写代码之前，先把“堆的大小关系”定死。我最常用的约定是：

• 左堆大小 = 右堆大小，或者左堆大小 = 右堆大小 + 1。
• 也就是说，奇数个数时，中位数单独放在左堆堆顶。

这个约定不是唯一的，有人喜欢右堆多一个，也有人喜欢总是在右堆取中位数。但你一定要固定一个，并且写代码时每一步都对照这个约定。我见过太多候选人代码写得很顺，但 heap 大小关系前后矛盾，最后 findMedian 里返回了错误的一边。

2.2 addNum 最稳的“三步走”写法

用 Python 写堆有个小别扭：标准库 heapq 只有最小堆，没有最大堆。技巧是存相反数。比如原始值 5 存成 -5，那么堆顶是最小的负值，对应的就是最大的原始值。

以 LeetCode 295 数据流的中位数为例，核心代码可以这样写：

import heapq class MedianFinder: def __init__(self): self.left = [] # 最大堆，存负值 self.right = [] # 最小堆，存正值 def addNum(self, num: int) -> None: # 第一步：新数先进左堆 heapq.heappush(self.left, -num) # 第二步：把左堆堆顶（左半边最大值）丢到右堆 heapq.heappush(self.right, -heapq.heappop(self.left)) # 第三步：如果左堆比右堆少，从右堆捞一个回来 if len(self.left) < len(self.right): heapq.heappush(self.left, -heapq.heappop(self.right)) def findMedian(self) -> float: if len(self.left) == len(self.right): return (-self.left[0] + self.right[0]) / 2.0 return float(-self.left[0])

这段代码的每一步都对应前面说的“先塞左边，再丢右边，不够再捞”。你可能会问：第一步直接塞左堆，第二步又从右堆把左堆最大值丢回去，是不是多此一举？不是。如果不经过这一步，新数到底属于左半边还是右半边，你必须额外判断；而经过“进左堆再弹出最大值丢右堆”，这个判断被堆自动完成了。这是一种“以空间换逻辑简单”的做法，非常推荐面试时用。

2.3 findMedian 是小事，但别写错返回类型

findMedian 看起来就是取堆顶，但有两个细节：

• 偶数个数时返回浮点数，一定要除以 2.0，不是除以 2。Python 里整数除法会直接截断。
• 奇数个数时，左堆堆顶存的是负值，要转回原始值再返回。

很多人在白板写代码时觉得这个题简单，最后挂在返回类型这种小事上，非常可惜。

2.4 完整实现与复杂度复盘

数据流中位数的时间复杂度：

这个复杂度为什么好？因为这意味着我们可以维护一个无限增长的数据流，任何时候想知道中位数，几乎是瞬间出结果。如果面试官追问“能不能更快”，你要知道从理论上讲，基于比较的插入结构最低就是 (O(\log n))，所以对顶堆已经是最优解之一。

3. 滑动窗口中位数：最难的不是堆，是删除

3.1 为什么排序法在滑动窗口里很快就不行了

如果说数据流中位数是对顶堆的入门，那么滑动窗口中位数就是对顶堆的进阶考验。题目一般是这样：给定一个数组 nums 和窗口大小 k，窗口每次往右移动一位，要求返回每个窗口的中位数。

最朴素的做法是每次截取窗口内 k 个数，排序取中位数。窗口移动 n 次，每次排序 (O(k\log k))，总复杂度 (O(n k \log k))。k 一旦上千，这题基本就废了。

更优的思路是沿用对顶堆：把所有窗口内元素按大小分成左右两半，堆顶提供中位数。窗口每次移动时，做两件事：删掉离开窗口的数，加入新进来的数。插入我们已经会了，真正的难点在“删除”。

3.2 堆的删除痛点与“延迟删除”设计

堆本身支持删除堆顶，但不支持直接删除任意元素。你要是想删掉一个不在堆顶的数，只能先标记它，等它慢慢浮到堆顶再真正弹出。这个技术叫延迟删除，英文一般叫 lazy deletion。

具体做法是维护一个哈希表，记录“已经被删除但还没从堆里真正弹出去的元素”以及它们的次数。比如窗口准备移动，旧元素 x 要离开，我不马上从堆里物理删除 x，而是delayed[x] += 1。等到某次查看堆顶时，如果堆顶元素恰好是 x，并且 delayed 里记着它，就把它弹出去，同时delayed[x] -= 1。如果堆顶不是 x，说明 x 还埋在堆里，暂时不影响中位数计算，那就留着。

这个思路很像现实里的“延迟发货”：订单先标记成取消，但货物还在仓库里，只有轮到这个货出库时才把它拦下来。它保证了堆的其他操作复杂度仍然是 (O(\log k))，只是多了一个哈希表的常数开销。

3.3 用 balance 维持双堆规模的诀窍

数据流中位数可以用len(left) < len(right)来平衡，但滑动窗口里有延迟删除，物理堆的大小可能和逻辑大小不一致。这时候再用 len 判断就不准了，需要额外用一个变量 balance 记录左右堆的逻辑大小差。

我约定 balance = 左堆逻辑大小 - 右堆逻辑大小。目标仍然是 balance 等于 0 或 1。于是每个滑动步骤变成这样：

• 旧元素离开：如果旧元素在左堆，balance 减 1；在右堆，balance 加 1。
• 新元素加入：如果新元素应该进左堆，balance 加 1；进右堆，balance 减 1。
• 最后根据 balance 的正负，往堆之间搬一个元素，并且每搬一次，balance 相应减 2 或加 2。

为什么要加 2？因为搬一个元素过去，一边少了 1，另一边多了 1，两边差距直接变化 2。这个细节很容易写错，面试时建议用一个小用例现场推一下。

3.4 滑动窗口中位数的完整实现

下面这份代码是 LeetCode 480 滑动窗口中位数的常见解法，我加了比较详细的注释：

from typing import List import heapq from collections import defaultdict class Solution: def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]: small = [] # 最大堆，存负值 large = [] # 最小堆，存正值 delayed = defaultdict(int) balance = 0 ans = [] def prune(heap, is_small): # 把堆顶已经标记为删除的元素真正弹出去 while heap: val = -heap[0] if is_small else heap[0] if delayed[val] > 0: delayed[val] -= 1 heapq.heappop(heap) else: break def make_balance(): nonlocal balance if balance > 0: # 左堆多了，把左堆堆顶挪到右堆 prune(small, True) heapq.heappush(large, -heapq.heappop(small)) balance -= 2 elif balance < 0: # 右堆多了，把右堆堆顶挪到左堆 prune(large, False) heapq.heappush(small, -heapq.heappop(large)) balance += 2 # 初始化第一个窗口 small = [-x for x in nums[:k]] heapq.heapify(small) large = [] for _ in range(k // 2): heapq.heappush(large, -heapq.heappop(small)) balance = len(small) - len(large) def get_median(): prune(small, True) prune(large, False) if k % 2 == 1: return float(-small[0]) return (-small[0] + large[0]) / 2.0 if k >= 1: ans.append(get_median()) for right in range(k, len(nums)): remove_val = nums[right - k] add_val = nums[right] # 比较前先清理堆顶，保证看到的是有效元素 prune(small, True) prune(large, False) # 旧元素逻辑删除 if not small or remove_val <= -small[0]: balance -= 1 else: balance += 1 delayed[remove_val] += 1 # 新元素插入 if not small or add_val <= -small[0]: heapq.heappush(small, -add_val) balance += 1 else: heapq.heappush(large, add_val) balance -= 1 make_balance() ans.append(get_median()) return ans

核心步骤我在前面都拆过，这里只强调几个容易出问题的地方：

• prune一定要在“判断元素属于哪一堆”之前调用。否则堆顶是一个已删除的脏元素，后续比较全部失真。
• small在极端情况下可能为空，所以判断条件写成not small or ...比较安全。
• make_balance里移动元素前也要prune，不然可能把一个已经标记删除的元素当成活元素搬走。

这里的get_median每轮都会做一次堆顶清理。你可能担心这样会不会把复杂度搞高。不会，因为每个元素最多被延迟标记一次、被真正弹出一次，全部加起来的均摊成本是 (O(\log k))，整体 (O(n\log k))。

3.5 窗口边界与重复元素：最容易翻车的地方

重复元素是这题的隐藏难点。如果窗口里有好几个相同的值，delayed 计数器就体现了价值。你不能用布尔值标记“这个元素删了”，因为堆里可能还有多个相同的值在排队。必须用计数。

比如 delayed[3] = 2，表示有两个 3 被标记删除但还没弹出。当堆顶遇到 3 时，每弹一次减 1，直到减成 0 才说明这个值的删除标记全部清空。

窗口边界也很容易翻车。移动窗口时，右指针从 k 开始，左指针对应 right - k。如果你在循环里把左右指针搞反，轻则结果错，重则数组越界。我建议每次写这种题都先画一个 k = 3 的小窗口，把下标对应关系写在纸上，再开始写循环。

4. 面试官视角：这道高频题到底在考察什么

4.1 一道题把排序、堆、滑动窗口全串起来

面试官喜欢拿这种题当高频题，因为它不像某些偏难怪题那样考察背诵，而是考察你能否把多个基础知识点串成一个完整方案。

你会不会先想到排序？会，这是人之常情。然后你能不能意识到排序在动态场景下代价太高？这是对复杂度的敏感度。你知不知道堆能高效维护堆顶极值？这是数据结构的基本功。你能不能想到用两个堆维护中位数？这是对“中位数本质上只关心中间位置”这个性质的理解。最后滑动窗口里的延迟删除，考验的是你在限制条件下灵活改造经典算法的能力。

这一连串问题下来，候选人是什么水平，基本就摸清了。

4.2 现场如何从“不会做”到“做出来”

如果你在面试现场第一次遇到这题，不要慌，按下面这个顺序走：

1. 先说暴力思路：每次排序，或者维护有序数组后二分插入。
2. 分析暴力思路的问题：排序太慢，有序数组插入是 (O(n))，数据量大时不行。
3. 问自己：能不能只维护中间位置？于是想到双堆。
4. 写出数据流版本的 addNum 和 findMedian。
5. 面试官加码到滑动窗口时，先想到删除是难点，再提出延迟删除。

这五步本身就是在向面试官展示你的思考过程。很多时候，最终代码是否一次通过不是最重要的，重要的是你有没有结构化地推进问题。

我甚至建议，即使你会做，也要在开头把“排序方案”提一句。面试官能看到你从朴素方案出发，而不是上来就背模板，这会让你的答案显得更可信。

4.3 常见错误清单和排查方法

我把这些年见过的高频 bug 整理成一张表：

如果你上线调不出来，最简单的排查方法是用小数据手动模拟。我用得最多的是这几个用例：

• 窗口 k = 1，输入 [1,2,3]，结果应该是 [1,2,3]。如果不对，说明删除和插入的边界乱了。
• 窗口 k = 2，输入 [1,2,3,4]，结果应该是 [1.5,2.5,3.5]。如果不对，说明偶数取平均那边有问题。
• 窗口 k = 3，输入 [1,3,-1,-3,5,3,6,7]，这是 LeetCode 官方示例，直接对照答案。

4.4 追问变体：数据量超大时的中位数

这是对顶堆场景最常见的追问。如果数据流非常大，甚至多个机器分布存储，你没法把所有数据丢进两个堆，怎么办？

常见的思路是引入分桶统计：维护值的频次分布，或者维护分位数近似。面试如果走到这里，重点不是让你实现一个完美的外部排序方案，而是考察你知不知道对顶堆的边界：它的空间是 (O(n))，必须存全量数据。一旦空间不够，就要用近似结构换精度。

你回答时可以说：“如果单机内存能放得下，对顶堆是最直接的选择；如果放不下，我会考虑分桶统计或者近似分位数，但精度会受影响。”这句话就能体现边界意识。

5. 我刷这道题到今天的一些实操心得

5.1 别背模板，背两个不变量

我一开始也走过背模板的弯路，但这题最大的问题是模板稍有改动就会崩。后来我发现，真正要记住的不是代码，而是两个不变量：

• 左堆所有元素小于等于右堆所有元素。
• 左右堆大小相差不超过 1，且中位数位置固定在左堆堆顶（或两堆顶平均）。

所有代码操作都是在维护这两个不变量。你每次写完一个函数，先停下来问自己：这两个条件现在还成立吗？成立，代码大概率没错；不成立，不需要看具体实现就知道 bug 在哪。

刷题的时候把这个思维练成条件反射，比背十遍代码都管用。

5.2 调试这类题最实用的小白鼠用例

除了 LeetCode 官方示例，我还会用一些极端用例来测自己的实现：

• 所有数字都相同，比如 [5,5,5,5,5]。这能检验延迟删除的计数逻辑，因为重复元素在窗口里频繁进出。
• 窗口大小等于数组长度，比如 nums = [1,2,3], k = 3。这要求初始化窗口的逻辑和后续滑动逻辑结果一致。
• 递增序列和递减序列各跑一遍，比如 [1,2,3,4,5] 和 [5,4,3,2,1]。这能暴露插入时比较方向写反的问题。
• 负数混合正数，比如 [-1,-2,3,4]。很多人最大堆存负值后，符号一多就晕，这个用例很有必要。

我每次写完这类题，都会把上面几个用例跑一遍，基本能把常见的错都堵住。

5.3 写在最后的一点个人建议

如果让我用一句话总结这次的分享，我会说：对顶堆不是一个需要死记硬背的数据结构，而是一种“把中位数问题拆成两个极值问题”的思维模型。

左堆维护极大值，右堆维护极小值，中间那条线就是中位数的位置。数据流版本让你掌握这个模型本身，滑动窗口版本让你掌握如何在动态删除的约束下改造模型。这两题连起来刷，价值远大于单刷两道题。

最后分享一个小习惯：每道用到堆的题，我都会坚持把“堆顶清理”“平衡条件”“复杂度摊还”这三件事单独写进题解笔记。等到面试前几天，不需要重新看整段代码，只需要看这几个关键词，就能快速把思路拉起来。希望这篇拆解也能成为你的题解笔记之一。