刷过LeetCode的人几乎都在同一个阶段碰见过这三样东西239题的滑动窗口最大值、347题的前K个高频元素以及那个总让你在到底该用大顶堆还是小顶堆之间反复纠结的堆。我一开始是把它们当三个独立知识点去背的——滑动窗口用双端队列高频元素用哈希加堆堆本身再单独看一遍课件。结果背完没几天就忘面试官换个问法就懵。直到后来我把三道题摊在同一张纸上复盘才发现它们根本不是三节课而是同一节课的三道练习在一个动态变化的数据集会里用尽可能低的复杂度去维护极值。这篇就把我复盘后的完整笔记摊开讲适合正在准备算法面试的人也适合一直没搞懂优先队列到底怎么用的人。不绕弯子直接上干货。1. 三题共通的内核为什么流式极值维护是面试官的宠儿1.1 动中取极值三道题的本质其实是一件事滑动窗口最大值表面上是双指针队列题但把它翻译成更抽象的语言一个数组从左往右滑过一个固定长度的窗口每滑一步就要知道窗口内当前最大的数。窗口在不断变化最大值也在不断变化你没法只算一次就完事。前K个高频元素的抽象版本是给一个序列先把它压成一个键值对集合再从这个集合里取权重最大的前K个。权重会重复、会很大你必须用某种结构在遍历一遍的过程中就把答案留出来。堆在这里的角色最直白它是专门为数据一直在变我要快速拿到当前极值设计的结构。堆顶就是答案代价只是每次改动后做一次对数时间的调整。所以这三道题放在一起看就很清晰堆是工具箱前K个高频元素是堆的典型应用场景而滑动窗口最大值是一道考你怎么甄别工具的题——它乍看也可以上堆但最优解偏偏是一个更轻量的单调队列。面试官把这三题连着问本质上就是在考察你脑子里有没有这条完整的工具链。1.2 复杂度意识面试官真正想听你算的账一个很现实的经验大部分人能写出暴力解法但只有一部分人能答出我的解法复杂度是多少瓶颈在哪里还能不能更快。后者才是面试官真正想听的东西。先建立一个规模感。假设n 10^5O(n^2)就是10^10次操作现代机器上大约要跑几十秒这在面试场景里就是超时。O(n log n)大约1.7 x 10^6次完全能接受。O(n)是最理想的情况。所以三个问题的暴力成本分别是多少问题暴力做法最坏复杂度滑动窗口最大值每个窗口扫描 k 个元素O((n-k1)*k)k 接近 n/2 时约 O(n²/4)前K个高频元素统计频率后全量排序O(n m log m)m 是不同元素的个数堆操作每次改动后重新找极值O(n) 每次显然不可行这个表列完你就能看出三道题优化的共同方向都是同一个把每次重新扫描变成维护一个一直在线更新的候选结构。后续所有代码都是围绕这件事展开的。1.3 空间换时间所有优化方案的共同交易数据结构层面所谓的优化几乎都是拿空间换时间。单调队列用 O(k) 的队列空间换掉每个窗口内 O(k) 的扫描堆用 O(K) 的堆空间换掉每次 O(m) 的全集扫描哈希表用 O(m) 的空间换掉 O(m²) 的查找。你只需要记住一句话不要每次都从头算把已经算过的中间结果缓存起来让答案能增量更新。这个思维模式比背题更重要。面试官从这三题中想确认的不是你记忆力好不好而是你有没有先算暴力复杂度再寻找增量维护方案的肌肉记忆。接下来的每一章我都会先讲为什么某个方案不行再讲正确的结构是怎么从不行里长出来的。2. 滑动窗口最大值单调双端队列的实战推演2.1 暴力法的成本账为什么 O(n*k) 会在第 51 个用例超时滑动窗口最大值暴力写起来只有三行def maxSlidingWindow_bruteforce(nums, k): return [max(nums[i:ik]) for i in range(len(nums) - k 1)]代码没问题问题在成本。窗口有n-k1个每个窗口求max要扫 k 个元素总操作量(n-k1)*k。取个真实数字感受一下n 100000k 50000窗口数量约 50001每个窗口扫描 50000 个元素算下来是 25 亿次比较。你的电脑再快在算法题的时间限制下也扛不住。这个复杂度不是说不能提而是提完你必须立刻意识到瓶颈是每个窗口里的 k 次比较优化目标就是把这个 k 压下去最好摊到 O(1)。这里的关键洞察是窗口每次只移动一格绝大部分元素是重叠的。上一个窗口的最大值和下一个窗口的最大值之间不是毫无关系的两次独立计算。一定有一种方式能复用前面的信息。2.2 单调队列的三条规则谁可以提前退休答案是用一个双端队列队列里存的是数组下标不是值。为什么必须存下标因为判断一个元素是否已经滑出窗口需要知道它的位置只存值的话你根本不知道它的寿命还剩多少。队列内部保持一个性质对应的数值从左到右严格单调递减队头永远是当前窗口最大值的下标。维护过程只有三条规则新元素nums[i]入队前从队尾弹出所有nums[队尾] nums[i]的下标。因为这些旧元素已经永远没有机会当窗口最大值了——新元素比它们大又比它们晚过期无论接下来窗口怎么滑新元素都会盖在它们前面。检查队头下标如果队头 i - k说明它已经滑出窗口左边界弹出。当窗口已经完整i k-1队头下标对应的值就是当前窗口的最大值。规则1可以这么理解想象窗口是一条传送带队列里排着几个身高递减的人。新来一个高个子他会把队尾那些比他矮的人全部挡住——因为高个子既在窗口里又更高还会更晚离开。那些矮个子从此再也不可能成为队头被看到不如直接出队。等到高个子自己过期滑出窗口那是他被淘汰的唯一理由。为什么队列保持的是单调递减而不是递增因为我们要的是最大值队头必须直接给出最大的那个。任何破坏单调性的元素都是噪音提前清除掉就好。2.3 代码实现、边界条件与 的选择题完整代码from collections import deque def maxSlidingWindow(nums: list[int], k: int) - list[int]: dq deque() ans [] for i, x in enumerate(nums): # 规则1弹出队尾所有“打不过”新元素的下标 while dq and nums[dq[-1]] x: dq.pop() dq.append(i) # 规则2过期下标出队 if dq[0] i - k: dq.popleft() # 规则3窗口完整时记录答案 if i k - 1: ans.append(nums[dq[0]]) return ans逐行说三个容易忽略的细节。第一规则1里我用了而不是。当新元素和队尾元素相等时新元素下标更靠右会在窗口里存活更久所以应该让新元素替代旧元素。用也能跑对但队列里会残留一批值相等但更早过期的旧下标代码行为不干净所以统一用。第二规则2的过期判断必须在规则3记录结果之前执行否则会把已经滑出窗口的元素写进答案这是新手最容易踩的坑。第三规则3用i k - 1判断窗口是否完整这是从0开始遍历的数组必须做的偏移。边界情况用一张表说明场景行为k 1窗口只有一个元素答案就是原数组本身k len(nums)只有一个窗口答案就是整个数组的最大值nums 为空直接返回空列表nums 全部相等每轮新元素替换旧元素队列里始终只有当前下标答案恒为那个值复杂度每个下标最多入队一次、出队一次均摊下来是 O(n)空间 O(k)。这一个 O(n) 相比暴力的 O(n*k)就是单调队列存在的全部价值。2.4 对照组用懒删除大顶堆也能做但没那么好我知道有人会问直接用一个大顶堆每次把元素扔进去取堆顶不就是最大值吗有什么难的确实可以做但要处理过期问题。堆只能弹出堆顶不能随手删掉窗口里任意一个元素所以要用懒删除堆里存(-值, 下标)每次取堆顶时如果发现下标已经滑出窗口就弹出去直到堆顶落在当前窗口内再取答案。import heapq def maxSlidingWindow_heap(nums, k): heap [] ans [] for i, x in enumerate(nums): heapq.heappush(heap, (-x, i)) # 懒删除弹出所有过期下标 while heap[0][1] i - k: heapq.heappop(heap) if i k - 1: ans.append(-heap[0][0]) return ans这个解法完全正确但复杂度是 O(n log n)因为堆每次调整要 log n。在 n 较大时会比单调队列的 O(n) 慢一个数量级。可是它值得学理由有二第一懒删除是很多堆类题的通用技巧以后做数据流中位数滑动窗口中位数都要用第二面试官如果在你讲完单调队列之后追问堆行不行你需要立刻答出这段对比而不是愣住。先能想到堆再论证它不如单调队列这比直接背出单调队列更能说明你真的理解问题。3. 大小顶堆先把堆这门课补上3.1 堆的底层形态一棵偏心但有序的完全二叉树很多人把大小顶堆记成一堆加减号规则一到写代码就乱。其实堆的底层非常朴素它是一棵用数组实现的完全二叉树同时满足一个堆序性质。大顶堆要求每个父节点的值不小于它的两个子节点所以根节点就是全局最大值小顶堆正好相反根节点是全局最小值。大顶堆和小顶堆本质上不是两种数据结构是同一个数据结构换了比较方向。在数组里下标i的父节点是(i-1)//2左孩子是2*i1右孩子是2*i2。这是堆的存储方式面试时能画出这棵树的形态、说出这三个下标公式就说明你不是在死记 API。我习惯把堆理解成一个偏心的结构它并不保证兄弟节点之间有序只保证父子之间有序。正因为约束比完全有序的数组弱得多它才能用 O(log n) 完成插入和删除如果堆像数组一样全有序插入就得 O(n)。这是堆和排序后取极值的本质区别。3.2 复杂度账本建堆、入堆、出堆分别花多少钱堆相关的复杂度是面试高频考题列成表操作时间复杂度说明push 入堆O(log n)新元素放到末尾向上比较交换pop 出堆O(log n)把堆顶和末尾交换后删除再向下调整peek 看堆顶O(1)直接取数组下标0建堆 heapifyO(n)从最后一个非叶子节点开始自底向上调整建堆是 O(n) 这一点很多初学者不信总觉得批量插入 n 次就是 O(n log n)。如果从叶子节点逐个向上 push确实是 O(n log n)但真正的建堆是heapify从倒数第二层开始每个节点向下调整。底层节点数量最多但下沉距离短根节点数量最少但下沉距离长。每一层的总工作量加起来是一个收敛的等比数列所以总代价是 O(n)。这个结论你最好能当场推导出来因为它经常作为堆的配套追问出现。3.3 语言里的堆Python 和 Java 的姿势差异写代码前先把语言差异讲清楚。Python 的heapq默认是小顶堆且不支持自定义比较器。想要大顶堆常规做法是存相反数入堆存-x出堆再取反。存元组时同理比如(-freq, element)就能按频率从高到低排序因为 Python 元组比较会先比较第一个元素。import heapq # 小顶堆 heap [] heapq.heappush(heap, 3) heapq.heappush(heap, 1) print(heapq.heappop(heap)) # 1 # 大顶堆存相反数 heapq.heappush(heap, -5) heapq.heappush(heap, -2) max_val -heapq.heappop(heap) # 5Java 的PriorityQueue默认也是小顶堆但支持Comparator// 小顶堆 PriorityQueueInteger minHeap new PriorityQueue(); // 大顶堆 PriorityQueueInteger maxHeap new PriorityQueue(Collections.reverseOrder()); // 存对象时用 lambda 指定比较键 PriorityQueueint[] heap new PriorityQueue((a, b) - a[1] - b[1]);Java 这里有个极容易翻车的地方(a, b) - a[1] - b[1]返回的是a - b行为是小顶堆想要大顶堆必须是b - a。很多人写反了结果 TopK 全取成了最小值。我的建议是写完后用一个三个元素的测试用例立刻验证堆顶是谁不要凭记忆判断方向。3.4 堆的筛选模式只保留 K 个候选内存和复杂度双赢在进入前K个高频元素之前先铺垫堆的一种高频用法——筛选模式。思路很简单维护一个固定大小为 K 的堆遍历所有数据时只做一件事如果新元素比堆顶更适合留下就替换堆顶否则直接丢弃。由于堆的大小始终是 K内存占用是 O(K)不受总数据量 m 影响。这个模式的核心价值在数据流场景。假设有一亿条日志想统计出现次数最多的 10 个错误码你不可能把所有日志装进内存再去排序但是你可以只维护一个大小为 10 的小顶堆日志一条一条进来堆永远只有 10 个元素。这就是为什么很多系统设计题里统计 TopK 的标准答案就是哈希计数 固定大小堆。第4章的代码就是这个模式的直接落地。4. 前K个高频元素哈希计数与堆筛选的组合拳4.1 第一步用哈希表摊平数据给定一个整数数组要统计每个元素出现的次数最直接的方式是哈希表from collections import Counter freq Counter(nums)freq是一个字典键是数组里的元素值是该元素出现的次数。这一步的时间复杂度是 O(n)空间 O(m)m 是不同元素的个数m ≤ n。这里有一个需要提前意识到的点后续堆的规模上限是 m 而不是 n因为频率表里每一个键才是有资格进堆的候选者重复出现的原始元素没有任何独立地位。这个认知差异会直接影响你在 k 很大时的边界处理。4.2 反直觉的答案为什么前K个最大反而要用小顶堆这是整道题最反直觉的地方。正常人看到前K个最大第一反应是把所有元素扔进大顶堆然后连续弹出 K 次堆顶。逻辑没问题但代价很贵你得把 m 个键值对全部存进堆里内存 O(m)还要做 m 次入堆操作再加 K 次出堆操作总复杂度 O(m K log m)。数据量小无所谓可一旦 m 达到百万级、K 只有 10这个方案的空间和时间都是浪费。正确做法是维护一个小顶堆只保留 K 个候选人。遍历频率表时当堆里不足 K 个元素直接入堆。当堆已满比较当前频率和堆顶频率如果当前频率大于堆顶就替换堆顶否则跳过。这时堆顶是当前 K 个候选人中最弱的一个也就是频率最小的那个。新来的元素如果连最弱的都打不过自然不配进前 K如果能打就把最弱的踢出去。整个过程下来堆里留下的恰好是频率最高的 K 个元素。可以类比一个只有 K 个座位的精英候选席。新人入场先看座位有没有空满了就和坐在最末尾的那位比成绩赢了就顶替输了就离开。这个机制保证任何时刻坐着的都是当前见过的最强的 K 个人。复杂度从 O(m K log m) 降到 O(m log K)空间从 O(m) 降到 O(K)。当 m 很大、K 很小时这个差距是决定性的。4.3 代码实现与输出顺序的坑完整代码import heapq from collections import Counter def topKFrequent(nums, k): freq Counter(nums) heap [] for num, f in freq.items(): if len(heap) k: heapq.heappush(heap, (f, num)) elif f heap[0][0]: heapq.heapreplace(heap, (f, num)) return [num for _, num in heap]heap中每个元素是(f, num)元组。Python 元组比较先比第一个元素 ff 相同再比 num完全符合需求。当堆满时用heapq.heapreplace一步完成弹出堆顶再压入新元素比heappop加heappush更简洁也保证堆的大小不超出 K。这里有一个非常容易踩的坑上面代码返回的[num for _, num in heap]只是前K个的集合不保证按频率从高到低排序。如果需要严格降序输出要先把堆里的元素全部弹出再反转res [] while heap: res.append(heapq.heappop(heap)[1]) res.reverse() return res面试时如果不确定面试官要什么顺序先问一句结果需要按频率排序吗这句话很加分。还有边界当 k 等于 len(freq) 时直接把频率表所有键返回即可不需要走堆逻辑k 小于等于 0 时直接返回空列表。这两个边界不处理代码会在极端用例上报错。4.4 进阶对比桶排序与快速选择以及它们为什么不是首选面试官如果继续追问还有更快的方案吗你可以抛出两个进阶解法。桶排序的思路既然频率最大不会超过数组长度 n就创建一个长度为 n1 的桶数组下标代表频率每个桶里放对应频率的元素。然后从后往前遍历桶累积取出 K 个元素。时间复杂度 O(n m)确实比堆的 O(m log K) 更快但空间要开辟 O(n) 的桶数组并且当频率分布很稀疏时浪费严重。它也不适合数据流场景因为必须等全部数据统计完才知道桶怎么划。快速选择的思路把频率当成一个数组用快速排序的 partition 思想找到第 K 大的位置平均时间 O(m)。但它最坏退化到 O(m²)而且同样不能在线处理流式数据。在算法题里可以作为更极端的优化提一嘴但工程上很少用它维护动态 TopK。解法时间复杂度空间复杂度支持流式工程友好度哈希 小顶堆O(m log K)O(m K)是高桶排序O(n m)O(n)否中快速选择O(m) 平均O(m)否低所以我的结论很明确面试默认答堆因为它简单、稳定、支持流式空间还小。桶排序和快速选择作为锦上添花的补充展示你知识面够宽而不是把它们当主答案。5. 面试连环炮三题连问时的高频追问与翻车细节5.1 追问一滑动窗口最大值能用堆吗能。我在 2.4 节写了一个懒删除大顶堆的解法它完全正确只是复杂度不如单调队列。面试官问这个问题通常不是让你推翻之前的单调队列而是看你能不能快速切换思路并准确说出两种方案的取舍。标准回答要包含三点第一堆能解决但要额外处理过期元素用存下标 懒删除第二堆解法复杂度 O(n log n)单调队列是 O(n)第三如果面试题不要求最优堆写起来反而更短、更容易在紧张时写对。把这三句话说完这道追问基本满分。5.2 追问二TopK 还能更快吗什么场景必须用堆如果面试官在你讲完堆解法后问还能不能更快先回答如果数据是静态的、可以全部读入内存用快速选择平均能到 O(m)桶排序能到 O(nm)然后立刻补一句但如果是数据流或内存不足以容纳全量数据堆是唯一能在线的方案。这句补话很关键它把你的答案从会做题提升到懂系统设计。举一个真实场景线上服务每秒产生大量访问日志要实时统计最近一小时访问量最高的 10 个 URL。数据永远不会一次性给全你必须一条一条处理这时只有定长小顶堆能维持一个实时更新的 Top10 榜单。任何先统计再排序的离线思路都不成立。想到这一层你就能理解为什么面试官总爱从这三道题一路问到系统设计。5.3 翻车现场我练了几十遍才避开的五个坑第一个坑是滑动窗口最大值里 deque 存值不存下标。存值确实能拿到最大值但窗口一滑你根本不知道这个值是否已经过期答案会乱套。解决方法是永远存下标取值时再去 nums 里查。第二个坑是 Java 的 Comparator 方向搞反把(a, b) - a[1] - b[1]当成大顶堆结果 TopK 取成全是最小值。写完一定用三个元素自测。第三个坑是 Python 大顶堆取反存pop 之后忘记再取反输出的全是负数。解决办法是封装一个小小的 helper 函数专门处理取反逻辑。第四个坑是前K个高频元素里用小顶堆却在遍历完成前就pop了一次导致堆里不足 K 个。记住筛选模式全程只替换堆顶不提前弹出。第五个坑是 k 比 freq 的长度还大直接返回所有键即可不需要堆硬走堆逻辑会得到错误结果。还有一个细节值得单独提heapreplace和heappushpop容易混。heapreplace(heap, item)是先弹出堆顶再压入新元素返回的是被弹出的旧堆顶heappushpop(heap, item)是先压入再弹出返回的是较大的那个。在筛掉最弱候选的场景里heapreplace更符合直觉但别忘了它的前提是堆已经满了。5.4 考前默写把三个套路收进短期记忆我自己的习惯是考试前不刷题用一分钟把套路表过一遍然后手写核心代码。这张表我默写了至少二十遍题型特征首选方案核心复杂度滑动窗口区间最值单调双端队列O(n)前K个最值数据全量可读哈希计数 小顶堆筛选O(n log K)前K个最值流式数据小顶堆筛选O(n log K)滑动窗口中位数大顶堆 小顶堆双堆O(n log n)静态数组第K大快速选择或堆O(n) 平均 / O(n log K)表的逻辑很简单要窗口内的最值就上单调队列要全局前K个就上定长堆要流式 TopK还是堆要中位数就左右各一个堆。覆盖了算法面试最高频的几个考点。写完这三道题我最大的体会是背答案没有意义把三个场景放进同一条思维链里理解才有意义。滑动窗口最大值不是记住双端队列,而是我意识到堆能解决但不够快所以用单调队列去掉 log n前K个高频元素不是记住小顶堆,而是我意识到只保留 K 个候选可以把内存和复杂度压到极致。下次你再默写这三段代码试试也像这样先想清楚为什么再动手指。保证比你对着题解敲三遍有效得多。