说实话基础算法集训走到第十六天滑动窗口这个专题是我当初最不以为然、后来打脸最狠的一课。刚听说这个概念时我想不就是一前一后两个指针吗有什么好集训一整天的结果第一道题就给我上了一课——暴力解跑了几秒没出结果换成滑动窗口后毫秒级出答案中间的差距就一个词滑动窗口。这篇内容不是从零讲原理而是把我第十六天集训真正消化掉的东西写出来滑动窗口的三种基本形态、最值问题里必须掌握的单调队列、它在网络和信号处理里的真实身份以及最容易让新手栽跟头的几个细节。适合正在刷LeetCode的人、准备算法面试的人也适合工作中想搞懂“滑动窗口限流”“滑动窗口滤波”到底是什么的工程师。1. 先从一道“超时”的题说起为什么暴力解会TLE我拿一道最普通的题入手给定一个整数数组 nums 和一个整数 k找出所有长度为 k 的连续子数组中和最大的那个。这题对应LeetCode 643的变体非常基础。如果第一次见到大多数人的第一反应都是暴力枚举起点 i从 i 加到 ik-1记录最大值。嵌套循环外层 n 个起点内层 k 个数字总复杂度 O(n×k)。当 n 和 k 都是 10^5 量级时运算量是 10^10C都要跑好几秒更别说Python。1.1 暴力解法为什么慢重复劳动是元凶我们看一个具体例子。nums [1, 4, 2, 10, 23, 3, 1, 0, 20]k 4。第一个窗口 [1,4,2,10] 的和是17第二个窗口 [4,2,10,23] 的和是39。注意看第一个窗口的后三个元素 [4,2,10] 和第二个窗口的前三个元素完全一样暴力解却把这三者在两个窗口里各加了一遍。窗口内容和窗口1[1, 4, 2, 10]17窗口2[4, 2, 10, 23]39重叠部分[4, 2, 10]被重复加了两次k4时重叠3个数k1000时重叠999个数。也就是说窗口每挪一步就有 k-1 个数字被重复求和。这就是暴力解慢的根本原因重复劳动。窗口越大浪费越严重。数据量一大TLE几乎是必然的。1.2 滑动窗口的核心思想一进一出结果接力滑动窗口的做法是先算出第一个窗口 [1,4,2,10] 的和记为 window_sum 17。窗口向右移动一步本质上只做两件事把新进来的 nums[4]23 加进来把离开的 nums[0]1 减掉。17 23 - 1 39刚好就是第二个窗口的和。整个过程不需要重新遍历 k 个数只需要一次加法和一次减法。这就是“一进一出”的状态复用。生活里也有这个例子你坐火车时透过车窗看风景窗口没变变的是风景。左边刚刚从视野里消失的景物右边新进入视野的景物中间部分你一直看在眼里——你当然不需要把整条风景线重新看一遍只需要感知“离开”和“进入”这两个变化就够了。def max_sum_of_fixed_window(nums: list[int], k: int) - int: if len(nums) k: return 0 window_sum sum(nums[:k]) max_sum window_sum for i in range(k, len(nums)): # 右边进一个新元素左边出一个旧元素 window_sum nums[i] - nums[i - k] max_sum max(max_sum, window_sum) return max_sum复杂度从 O(n×k) 降到 O(n)没有额外空间。这就是滑动窗口最核心的形态一个长度为 k 的窗口每步右移一格窗口内容的变化只有左端出、右端进。提示滑动窗口并不是某种高深的数据结构它本质上是一种枚举策略的优化——用“复用上一次的计算结果”来减少重复工作量。2. 窗口不只一种固定长度、可变长度、计数类很多人学滑动窗口卡住是因为以为窗口永远是定长的。其实窗口的长度本身经常是变量需要在移动过程中动态决定扩大还是收缩。我习惯把滑动窗口分成三种形态来掌握固定长度窗口、可变长度窗口、计数类窗口。三种形态的右指针动作基本类似差别全在左指针的收缩时机和辅助变量的维护方式上。2.1 固定长度窗口先加右边再判断是否删左边固定长度窗口就是窗口大小 k 在题目里是给定的比如前面那道求和题、LeetCode 643、LeetCode 239最大值。模板其实很单调右指针每次固定右移一格当窗口长度超过 k 之后左指针也跟着每步右移一格始终维持窗口长度等于 k。def fixed_window(nums, k): left 0 # 假定需要维护某种窗口状态比如 sum、count、max等 for right in range(len(nums)): # 1. 把 nums[right] 纳入窗口 add(nums[right]) # 2. 当窗口长度超过 k 时左指针前移 if right - left 1 k: remove(nums[left]) left 1 # 3. 窗口长度恰好为 k 时记录答案 if right - left 1 k: # 记录答案 pass注意顺序先加右侧再判断是否需要删左侧最后在长度恰好为 k 时记录。我见过很多人喜欢先写 left 再写 right顺序一乱窗口里的内容就跟实际对不上。2.2 可变长度窗口什么时候扩大什么时候收缩可变长度窗口是滑动窗口题里的大头典型如 LeetCode 3 无重复字符的最长子串、LeetCode 209 长度最小的子数组。这类题的策略要从目标出发分两类看。第一类求最长。目标是让窗口尽可能长所以右指针无脑往前走把新字符加进窗口一旦窗口内出现重复字符左指针就往前走直到没有重复为止。每一步都更新答案。第二类求最短。要求子数组和 target 的最短长度策略相反右指针往前走直到窗口内和 target一旦满足条件就尝试收缩左指针看能不能再短一点收缩到不满足为止再继续扩展右指针。类型右指针动作左指针收缩条件何时更新答案求最长无脑右移条件被破坏后收缩到恢复每次右移后求最短无脑右移直到满足目标满足目标后尽可能收缩每次收缩后、仍满足时拿 LeetCode 209 举例这是最典型的“求最短”模板def minSubArrayLen(target: int, nums: list[int]) - int: left 0 window_sum 0 ans float(inf) for right in range(len(nums)): window_sum nums[right] # 扩大窗口 while window_sum target: # 满足条件尝试收缩 ans min(ans, right - left 1) window_sum - nums[left] left 1 return 0 if ans float(inf) else ans再看 LeetCode 3这是“求最长”的模板def lengthOfLongestSubstring(s: str) - int: left 0 seen set() ans 0 for right in range(len(s)): # 有重复收缩左边界直到没有重复 while s[right] in seen: seen.remove(s[left]) left 1 seen.add(s[right]) ans max(ans, right - left 1) return ans注意两个模板的差异求最短用 while 收缩且收缩过程中持续更新答案求最长是收缩到条件满足就停更新放在收缩之后。很多人在“求最短”里把 while 写成 if收缩不彻底算出来的长度偏大这是最常见的错误之一。2.3 计数类窗口用哈希表或数组当账本有些题光靠 set 不够因为窗口里允许出现重复元素而且这些重复元素的个数直接影响答案。比如最小覆盖子串LeetCode 76、字符串排列LeetCode 567、找所有字母异位词LeetCode 438。这类题本质上还是滑动窗口但辅助变量从 set 变成了哈希表或计数数组用来记录窗口里每个元素的出现次数相当于给窗口内容记一本“账”。以 LeetCode 438 为例在 s 中找所有 p 的异位词窗口长度固定等于 len(p)需要比较窗口内的字符计数和 p 的字符计数。因为题目限定是小写字母直接用长度26的数组比哈希表更快。def findAnagrams(s: str, p: str) - list[int]: need [0] * 26 for ch in p: need[ord(ch) - 97] 1 window [0] * 26 left 0 ans [] for right in range(len(s)): window[ord(s[right]) - 97] 1 # 窗口长度达到 len(p) 时检查并移动左指针 if right - left 1 len(p): if window need: ans.append(left) window[ord(s[left]) - 97] - 1 left 1 return ans为什么数组能当账本因为字符只有26种每个位置存对应字符的出现次数窗口移动时右侧字符的计数加一左侧字符的计数减一账本始终保持“当前窗口内容”的准确描述。Python 里两个 list 可以直接比较相等写起来非常顺手这也是计数数组相对哈希表的优势。3. 窗口内快速求最值单调队列的登场前面说了窗口的“和”维护起来很容易因为求和满足可逆运算加进来一个数、减掉一个数答案马上更新。但最大值没有这种“减法”。你不能说“窗口最大值出去了一个数我再给它减掉什么”最大值没有逆运算。所以需要额外的数据结构来回答当前窗口内的最大值是什么3.1 为什么需要单调队列最大值没有“减法”最容易想到的是堆优先队列。把窗口内所有元素扔进一个大顶堆堆顶就是最大值。但窗口一直在移动左端被移出的元素还残留在堆里堆不支持精确删除任意一个元素。要解决就得“延迟删除”每次取堆顶时检查这个元素的下标是否还在当前窗口内不在就弹出直到堆顶合法。这样的复杂度是 O(n log k)代码也啰嗦。单调队列是另一种思路既然堆麻烦在“删不掉旧元素”那我们就让队列里天然只剩可能成为最大值的候选者。维护一个双端队列从队头到队尾元素对应在数组中的下标是递增的值严格递减。也就是说队头永远是当前窗口的最大值。3.2 单调队列的维护规则与代码模板以 LeetCode 239 滑动窗口最大值为例核心操作分三步新元素从队尾入队前先把队尾所有 新元素的值全部弹出。为什么可以弹因为它们比新元素小而且下标更老会比新元素更早离开窗口。新元素既比它们大、又比它们活得久它们无论如何都不可能再成为后续某个窗口的最大值候选留着纯属浪费空间。把新元素的下标从队尾入队。检查队头如果队头下标已经滑出当前窗口队头下标 i - k将其弹出。此时队头就是当前窗口的最大值。from collections import deque def maxSlidingWindow(nums: list[int], k: int) - list[int]: q deque() # 存下标从队头到队尾对应的值单调递减 ans [] for i, x in enumerate(nums): # 1. 维护单调性弹出队尾所有 x 的下标 while q and nums[q[-1]] x: q.pop() q.append(i) # 2. 弹出已经离开窗口的队头 if q[0] i - k: q.popleft() # 3. 窗口成型后记录答案 if i k - 1: ans.append(nums[q[0]]) return ans这段代码非常短但信息密度很大。我用 nums [1,3,-1,-3,5,3,6,7]k3 完整走一遍i元素入队前操作入队后队列下标 / 值队头是否出窗窗口最大值01队空直接入[0] / [1]否-13队尾值1 3弹出0再入1[1] / [3]否-2-1队尾值3 -1直接入2[1,2] / [3,-1]否33-3队尾值-1 -3直接入3[1,2,3] / [3,-1,-3]否345弹出 -3、-1、3再入4[4] / [5]否553队尾值5 3直接入5[4,5] / [5,3]否566弹出3、5再入6[6] / [6]否677弹出6再入7[7] / [7]否7第4行是关键新元素5进入时队里剩余 [3,-1,-3] 全都 5而且它们都比5“老”于是被全部弹出。队列里没保留任何旧元素但最大值5依然在队头。每个元素最多进队一次、出队一次整体均摊 O(n)。提示单调队列不是“排序队列”队列里不一定覆盖窗口内所有元素它只保留“可能成为最大值的候选者”。这个认知很重要很多人误以为单调队列把窗口内元素全部有序存了一遍其实不是。3.3 和堆优先队列的对比都是延迟删除差别在哪从实际面试和工程角度看用堆也能解滑动窗口最大值但和单调队列的取舍差异很大。堆做法的Python实现长这样def maxSlidingWindow_heap(nums, k): import heapq heap [(-nums[i], i) for i in range(k)] heapq.heapify(heap) ans [-heap[0][0]] for i in range(k, len(nums)): heapq.heappush(heap, (-nums[i], i)) # 延迟删除弹出所有不在窗口内的堆顶 while heap[0][1] i - k: heapq.heappop(heap) ans.append(-heap[0][0]) return ans堆的麻烦在于你永远不知道堆顶是不是“幽灵元素”只能取的时候一个个验货。单调队列则是入队时就主动淘汰无用元素取的时候直接取队头清爽很多。项目单调队列优先队列堆取最值方向只能快速取最大值或最小值看维护递增还是递减可以取最大或最小单次操作均摊O(1)O(log k)旧元素处理方式入队时从队尾弹出无用元素取堆顶时延迟删除代码量短一个双端队列即可略长需要存下标适用场景窗口最值、单调性明显的区间问题动态增删且需要修改优先级的场景我个人偏好只要题目明确要求“窗口内最值”优先考虑单调队列。代码更短、常数更小面试讲起来也更清晰。4. 滑动窗口不只是算法题它藏在网络、限流和信号处理里很多人刷完滑动窗口觉得这东西只活在LeetCode里。其实“滑动窗口”这个名字本身就是从工程里来的——网络协议、服务端限流、信号滤波全都在用它。理解这些场景反过来能帮你更好地理解算法题里的窗口。4.1 网络中的滑动窗口TCP可靠传输的“在途额度”学网络时一定会碰到 TCP 的滑动窗口。发送方维护一个窗口窗口内的数据是可以发送或已经发送但未确认的收到 ACK 后窗口向右滑动新数据才能进入窗口。为什么叫“窗口”因为发送方不需要等每个包都确认再发下一个而是允许一批包“在途”窗口大小就是没有收到确认还能继续发送的额度。窗口越大吞吐越高但太大也可能造成网络拥塞。重传协议里的 Go-Back-N 和 Selective Repeat 也是滑动窗口思想Go-Back-N 是窗口内如果有一个包丢失就回退重传后面所有包Selective Repeat 是只重传丢失的那一个。两者的差别在于对窗口内错误包的处理粒度。这个场景和算法题里“窗口移动”最像的地方在于你永远只关注窗口内这一段数据的状态窗口外的数据要么是过去式要么是未来式。4.2 服务端限流里的滑窗从固定窗口到滑动窗口后端做接口限流时最朴素的做法是固定窗口1秒内最多100次请求超过就拒绝。实现简单但有一个非常经典的临界问题如果第0.9秒来了100个请求第1.1秒又来了100个请求这两个时段各自都“合法”可实际上在0.2秒内打进来了200个请求——限流形同虚设。滑动窗口限流就是让窗口随时间平滑滚动维护最近一个时间窗口比如最近1秒的请求记录新请求进来时先把窗口外的旧请求弹出再判断当前窗口内计数是否达到阈值。用代码实现就是一套很熟悉的滑动窗口模板from collections import deque import time class SlidingWindowLimiter: def __init__(self, max_requests: int, window_seconds: float): self.max_requests max_requests self.window_seconds window_seconds self.requests deque() def allow(self) - bool: now time.time() # 弹出窗口外的旧请求 while self.requests and now - self.requests[0] self.window_seconds: self.requests.popleft() if len(self.requests) self.max_requests: self.requests.append(now) return True return False这段代码的思想和 LeetCode 209 几乎一模一样右端是当前请求时刻左端是过期请求收缩条件是“是否已经超出时间窗口”。算法题里的技巧直接平移到了生产环境。4.3 信号处理中的滑窗滑动窗口滤波怎么做信号处理里最常用的平滑手段之一就是滑动窗口滤波也叫移动平均滤波。传感器采集到的信号往往夹杂着高频噪声工程上最简单的处理是取最近 N 个样本的平均值作为输出y[n] (x[n] x[n-1] ... x[n-N1]) / N每来一个新样本窗口就往前滑动一格。这个公式和第一题的子数组和几乎相同只是用途从“求最大”变成了“求平均/去噪”。既然有和就有递推关系y_new y_old (x_new - x_old) / N只需要一次加法和一次除法就能更新滑动窗口的平均值不用重新加 N 个数。这在资源受限的嵌入式设备上非常宝贵。窗口大小 N 的选择是个典型权衡N 太小平滑效果差噪声压不住N 太大输出平滑了但响应变慢滞后明显。这就是热搜词里“滑动窗口滤波器延迟”的来源——滑动窗口滤波对输入的响应会有约 (N-1)/2 个采样周期的额外延迟窗口越长延迟越大。面试被问到“为什么移动平均会有延迟”答出这一点就够了。如果在 FPGA 里做滑动窗口滤波常见做法是移位寄存器存 N 个最新样本配合一个累加器每来一个新时钟数据移出、新数据移入累加器做一次“加新减旧”就得到新的和再除以 N 得到均值。这本质上就是把算法题的“一进一出”落到了硬件流水线上。热搜词“滑动窗口滤波verilog”指的就是这个实现思路。def moving_average(data: list[float], window_size: int) - list[float]: if len(data) window_size: return [] avg sum(data[:window_size]) / window_size result [avg] for i in range(window_size, len(data)): # 递推新均值 旧均值 (新样本 - 旧样本) / N avg (data[i] - data[i - window_size]) / window_size result.append(avg) return result5. 集训第十六天的个人经验易错点与刷题路线到了集训后半段我觉得比“会写模板”更重要的是“知道哪里会写错”。滑动窗口的代码量不大但细节非常密集一个操作顺序不对结果就全乱。这里把我踩过的坑和验证过的刷题路线一并写出来。5.1 最容易踩的四个坑第一个坑左指针移动时机搞错。固定窗口是先加右边、再判断是否需要删左边可变窗口求最短时是用 while 持续收缩。很多新手把 while 写成 if收缩不彻底答案偏大。比如 LeetCode 209如果只用 if窗口可能收缩一次就停算出来的最短长度往往不对。第二个坑辅助变量没同步。用 sum、count、set 记录窗口内容时每次 left/right 移动都必须同步更新辅助变量。漏掉 remove 的后果是窗口里有“幽灵元素”答案全错。我见过不少人调了半小时 bug最后发现问题就是 set 里忘了 remove。第三个坑死循环。左指针可能越过右指针尤其在使用 while 收缩时。要保证 left 始终小于等于 right并且注意题目的边界条件比如 LeetCode 209 中 nums 全是正数才能保证 while 一定收敛如果 target 0要单独处理。第四个坑窗口还没成型就开始记录答案。固定长度窗口必须等 right - left 1 k 时才记录。很多人喜欢用 i k 判断但窗口内容是从 i-k1 到 i下标容易差一位。建议统一用 right - left 1 这个判定一眼就能看出来窗口是否成型。分享一个我自己最常用的调试方法把每步移动后的 left、right、window_sum 或队列内容打印出来肉眼跑几轮问题基本就暴露了。滑动窗口的 bug 是典型的“看得见的 bug”打印比死盯代码高效得多。5.2 滑动窗口刷题路线从入门到进阶以下是我自己训练时验证过的顺序从固定窗口到可变窗口再到带辅助结构的窗口难度平缓上升阶段题目考察点入门LeetCode 643 子数组最大平均数 I固定窗口求和入门LeetCode 3 无重复字符的最长子串可变窗口 set入门LeetCode 209 长度最小的子数组可变窗口求最短进阶LeetCode 438 找到字符串中所有字母异位词固定窗口 计数数组进阶LeetCode 567 字符串的排列固定窗口 计数数组进阶LeetCode 239 滑动窗口最大值单调队列进阶LeetCode 76 最小覆盖子串可变窗口 哈希记账提高LeetCode 424 替换后的最长重复字符窗口内众数维护提高LeetCode 992 K个不同整数的子数组恰好K个 atMost(K) - atMost(K-1)提高LeetCode 480 滑动窗口中位数滑窗 双堆 / 有序结构每道题建议先别急着写码用手在纸上推一遍窗口移动过程。尤其是 239 这种单调队列题手推两遍之后你才能真正理解为什么队尾要弹出“老且小”的元素。5.3 第十六天集训的最后体会第十六天那天晚上我把 LeetCode 239 的单调队列代码关了屏幕默写写错了三遍才完全记住每个操作背后的“为什么”。这件事给我的触动挺大滑动窗口的模板不难背难的是理解每个操作出现的时机。对我个人来说最有效的方法是把窗口移动想象成一条流水线——右边进一个零件左边出一件成品中间的工位状态必须在一进一出之间保持一致。最后分享一个我一直沿用的技巧遇到滑动窗口题先问自己三个问题。第一窗口是固定长度还是可变长度第二辅助变量要不要支持快速最值或者需要记录计数第三答案在什么时候记录是每次移动后还是收缩完成后把这三个问题答清楚代码基本就出来了。这就是我第十六天集训沉淀下来的最核心的东西。 
长河君 · 2026/10/10 22:29:07 · 阅读 1.2k 滑动窗口算法全解析：三种形态、单调队列与工程应用
说实话基础算法集训走到第十六天滑动窗口这个专题是我当初最不以为然、后来打脸最狠的一课。刚听说这个概念时我想不就是一前一后两个指针吗有什么好集训一整天的结果第一道题就给我上了一课——暴力解跑了几秒没出结果换成滑动窗口后毫秒级出答案中间的差距就一个词滑动窗口。这篇内容不是从零讲原理而是把我第十六天集训真正消化掉的东西写出来滑动窗口的三种基本形态、最值问题里必须掌握的单调队列、它在网络和信号处理里的真实身份以及最容易让新手栽跟头的几个细节。适合正在刷LeetCode的人、准备算法面试的人也适合工作中想搞懂“滑动窗口限流”“滑动窗口滤波”到底是什么的工程师。1. 先从一道“超时”的题说起为什么暴力解会TLE我拿一道最普通的题入手给定一个整数数组 nums 和一个整数 k找出所有长度为 k 的连续子数组中和最大的那个。这题对应LeetCode 643的变体非常基础。如果第一次见到大多数人的第一反应都是暴力枚举起点 i从 i 加到 ik-1记录最大值。嵌套循环外层 n 个起点内层 k 个数字总复杂度 O(n×k)。当 n 和 k 都是 10^5 量级时运算量是 10^10C都要跑好几秒更别说Python。1.1 暴力解法为什么慢重复劳动是元凶我们看一个具体例子。nums [1, 4, 2, 10, 23, 3, 1, 0, 20]k 4。第一个窗口 [1,4,2,10] 的和是17第二个窗口 [4,2,10,23] 的和是39。注意看第一个窗口的后三个元素 [4,2,10] 和第二个窗口的前三个元素完全一样暴力解却把这三者在两个窗口里各加了一遍。窗口内容和窗口1[1, 4, 2, 10]17窗口2[4, 2, 10, 23]39重叠部分[4, 2, 10]被重复加了两次k4时重叠3个数k1000时重叠999个数。也就是说窗口每挪一步就有 k-1 个数字被重复求和。这就是暴力解慢的根本原因重复劳动。窗口越大浪费越严重。数据量一大TLE几乎是必然的。1.2 滑动窗口的核心思想一进一出结果接力滑动窗口的做法是先算出第一个窗口 [1,4,2,10] 的和记为 window_sum 17。窗口向右移动一步本质上只做两件事把新进来的 nums[4]23 加进来把离开的 nums[0]1 减掉。17 23 - 1 39刚好就是第二个窗口的和。整个过程不需要重新遍历 k 个数只需要一次加法和一次减法。这就是“一进一出”的状态复用。生活里也有这个例子你坐火车时透过车窗看风景窗口没变变的是风景。左边刚刚从视野里消失的景物右边新进入视野的景物中间部分你一直看在眼里——你当然不需要把整条风景线重新看一遍只需要感知“离开”和“进入”这两个变化就够了。def max_sum_of_fixed_window(nums: list[int], k: int) - int: if len(nums) k: return 0 window_sum sum(nums[:k]) max_sum window_sum for i in range(k, len(nums)): # 右边进一个新元素左边出一个旧元素 window_sum nums[i] - nums[i - k] max_sum max(max_sum, window_sum) return max_sum复杂度从 O(n×k) 降到 O(n)没有额外空间。这就是滑动窗口最核心的形态一个长度为 k 的窗口每步右移一格窗口内容的变化只有左端出、右端进。提示滑动窗口并不是某种高深的数据结构它本质上是一种枚举策略的优化——用“复用上一次的计算结果”来减少重复工作量。2. 窗口不只一种固定长度、可变长度、计数类很多人学滑动窗口卡住是因为以为窗口永远是定长的。其实窗口的长度本身经常是变量需要在移动过程中动态决定扩大还是收缩。我习惯把滑动窗口分成三种形态来掌握固定长度窗口、可变长度窗口、计数类窗口。三种形态的右指针动作基本类似差别全在左指针的收缩时机和辅助变量的维护方式上。2.1 固定长度窗口先加右边再判断是否删左边固定长度窗口就是窗口大小 k 在题目里是给定的比如前面那道求和题、LeetCode 643、LeetCode 239最大值。模板其实很单调右指针每次固定右移一格当窗口长度超过 k 之后左指针也跟着每步右移一格始终维持窗口长度等于 k。def fixed_window(nums, k): left 0 # 假定需要维护某种窗口状态比如 sum、count、max等 for right in range(len(nums)): # 1. 把 nums[right] 纳入窗口 add(nums[right]) # 2. 当窗口长度超过 k 时左指针前移 if right - left 1 k: remove(nums[left]) left 1 # 3. 窗口长度恰好为 k 时记录答案 if right - left 1 k: # 记录答案 pass注意顺序先加右侧再判断是否需要删左侧最后在长度恰好为 k 时记录。我见过很多人喜欢先写 left 再写 right顺序一乱窗口里的内容就跟实际对不上。2.2 可变长度窗口什么时候扩大什么时候收缩可变长度窗口是滑动窗口题里的大头典型如 LeetCode 3 无重复字符的最长子串、LeetCode 209 长度最小的子数组。这类题的策略要从目标出发分两类看。第一类求最长。目标是让窗口尽可能长所以右指针无脑往前走把新字符加进窗口一旦窗口内出现重复字符左指针就往前走直到没有重复为止。每一步都更新答案。第二类求最短。要求子数组和 target 的最短长度策略相反右指针往前走直到窗口内和 target一旦满足条件就尝试收缩左指针看能不能再短一点收缩到不满足为止再继续扩展右指针。类型右指针动作左指针收缩条件何时更新答案求最长无脑右移条件被破坏后收缩到恢复每次右移后求最短无脑右移直到满足目标满足目标后尽可能收缩每次收缩后、仍满足时拿 LeetCode 209 举例这是最典型的“求最短”模板def minSubArrayLen(target: int, nums: list[int]) - int: left 0 window_sum 0 ans float(inf) for right in range(len(nums)): window_sum nums[right] # 扩大窗口 while window_sum target: # 满足条件尝试收缩 ans min(ans, right - left 1) window_sum - nums[left] left 1 return 0 if ans float(inf) else ans再看 LeetCode 3这是“求最长”的模板def lengthOfLongestSubstring(s: str) - int: left 0 seen set() ans 0 for right in range(len(s)): # 有重复收缩左边界直到没有重复 while s[right] in seen: seen.remove(s[left]) left 1 seen.add(s[right]) ans max(ans, right - left 1) return ans注意两个模板的差异求最短用 while 收缩且收缩过程中持续更新答案求最长是收缩到条件满足就停更新放在收缩之后。很多人在“求最短”里把 while 写成 if收缩不彻底算出来的长度偏大这是最常见的错误之一。2.3 计数类窗口用哈希表或数组当账本有些题光靠 set 不够因为窗口里允许出现重复元素而且这些重复元素的个数直接影响答案。比如最小覆盖子串LeetCode 76、字符串排列LeetCode 567、找所有字母异位词LeetCode 438。这类题本质上还是滑动窗口但辅助变量从 set 变成了哈希表或计数数组用来记录窗口里每个元素的出现次数相当于给窗口内容记一本“账”。以 LeetCode 438 为例在 s 中找所有 p 的异位词窗口长度固定等于 len(p)需要比较窗口内的字符计数和 p 的字符计数。因为题目限定是小写字母直接用长度26的数组比哈希表更快。def findAnagrams(s: str, p: str) - list[int]: need [0] * 26 for ch in p: need[ord(ch) - 97] 1 window [0] * 26 left 0 ans [] for right in range(len(s)): window[ord(s[right]) - 97] 1 # 窗口长度达到 len(p) 时检查并移动左指针 if right - left 1 len(p): if window need: ans.append(left) window[ord(s[left]) - 97] - 1 left 1 return ans为什么数组能当账本因为字符只有26种每个位置存对应字符的出现次数窗口移动时右侧字符的计数加一左侧字符的计数减一账本始终保持“当前窗口内容”的准确描述。Python 里两个 list 可以直接比较相等写起来非常顺手这也是计数数组相对哈希表的优势。3. 窗口内快速求最值单调队列的登场前面说了窗口的“和”维护起来很容易因为求和满足可逆运算加进来一个数、减掉一个数答案马上更新。但最大值没有这种“减法”。你不能说“窗口最大值出去了一个数我再给它减掉什么”最大值没有逆运算。所以需要额外的数据结构来回答当前窗口内的最大值是什么3.1 为什么需要单调队列最大值没有“减法”最容易想到的是堆优先队列。把窗口内所有元素扔进一个大顶堆堆顶就是最大值。但窗口一直在移动左端被移出的元素还残留在堆里堆不支持精确删除任意一个元素。要解决就得“延迟删除”每次取堆顶时检查这个元素的下标是否还在当前窗口内不在就弹出直到堆顶合法。这样的复杂度是 O(n log k)代码也啰嗦。单调队列是另一种思路既然堆麻烦在“删不掉旧元素”那我们就让队列里天然只剩可能成为最大值的候选者。维护一个双端队列从队头到队尾元素对应在数组中的下标是递增的值严格递减。也就是说队头永远是当前窗口的最大值。3.2 单调队列的维护规则与代码模板以 LeetCode 239 滑动窗口最大值为例核心操作分三步新元素从队尾入队前先把队尾所有 新元素的值全部弹出。为什么可以弹因为它们比新元素小而且下标更老会比新元素更早离开窗口。新元素既比它们大、又比它们活得久它们无论如何都不可能再成为后续某个窗口的最大值候选留着纯属浪费空间。把新元素的下标从队尾入队。检查队头如果队头下标已经滑出当前窗口队头下标 i - k将其弹出。此时队头就是当前窗口的最大值。from collections import deque def maxSlidingWindow(nums: list[int], k: int) - list[int]: q deque() # 存下标从队头到队尾对应的值单调递减 ans [] for i, x in enumerate(nums): # 1. 维护单调性弹出队尾所有 x 的下标 while q and nums[q[-1]] x: q.pop() q.append(i) # 2. 弹出已经离开窗口的队头 if q[0] i - k: q.popleft() # 3. 窗口成型后记录答案 if i k - 1: ans.append(nums[q[0]]) return ans这段代码非常短但信息密度很大。我用 nums [1,3,-1,-3,5,3,6,7]k3 完整走一遍i元素入队前操作入队后队列下标 / 值队头是否出窗窗口最大值01队空直接入[0] / [1]否-13队尾值1 3弹出0再入1[1] / [3]否-2-1队尾值3 -1直接入2[1,2] / [3,-1]否33-3队尾值-1 -3直接入3[1,2,3] / [3,-1,-3]否345弹出 -3、-1、3再入4[4] / [5]否553队尾值5 3直接入5[4,5] / [5,3]否566弹出3、5再入6[6] / [6]否677弹出6再入7[7] / [7]否7第4行是关键新元素5进入时队里剩余 [3,-1,-3] 全都 5而且它们都比5“老”于是被全部弹出。队列里没保留任何旧元素但最大值5依然在队头。每个元素最多进队一次、出队一次整体均摊 O(n)。提示单调队列不是“排序队列”队列里不一定覆盖窗口内所有元素它只保留“可能成为最大值的候选者”。这个认知很重要很多人误以为单调队列把窗口内元素全部有序存了一遍其实不是。3.3 和堆优先队列的对比都是延迟删除差别在哪从实际面试和工程角度看用堆也能解滑动窗口最大值但和单调队列的取舍差异很大。堆做法的Python实现长这样def maxSlidingWindow_heap(nums, k): import heapq heap [(-nums[i], i) for i in range(k)] heapq.heapify(heap) ans [-heap[0][0]] for i in range(k, len(nums)): heapq.heappush(heap, (-nums[i], i)) # 延迟删除弹出所有不在窗口内的堆顶 while heap[0][1] i - k: heapq.heappop(heap) ans.append(-heap[0][0]) return ans堆的麻烦在于你永远不知道堆顶是不是“幽灵元素”只能取的时候一个个验货。单调队列则是入队时就主动淘汰无用元素取的时候直接取队头清爽很多。项目单调队列优先队列堆取最值方向只能快速取最大值或最小值看维护递增还是递减可以取最大或最小单次操作均摊O(1)O(log k)旧元素处理方式入队时从队尾弹出无用元素取堆顶时延迟删除代码量短一个双端队列即可略长需要存下标适用场景窗口最值、单调性明显的区间问题动态增删且需要修改优先级的场景我个人偏好只要题目明确要求“窗口内最值”优先考虑单调队列。代码更短、常数更小面试讲起来也更清晰。4. 滑动窗口不只是算法题它藏在网络、限流和信号处理里很多人刷完滑动窗口觉得这东西只活在LeetCode里。其实“滑动窗口”这个名字本身就是从工程里来的——网络协议、服务端限流、信号滤波全都在用它。理解这些场景反过来能帮你更好地理解算法题里的窗口。4.1 网络中的滑动窗口TCP可靠传输的“在途额度”学网络时一定会碰到 TCP 的滑动窗口。发送方维护一个窗口窗口内的数据是可以发送或已经发送但未确认的收到 ACK 后窗口向右滑动新数据才能进入窗口。为什么叫“窗口”因为发送方不需要等每个包都确认再发下一个而是允许一批包“在途”窗口大小就是没有收到确认还能继续发送的额度。窗口越大吞吐越高但太大也可能造成网络拥塞。重传协议里的 Go-Back-N 和 Selective Repeat 也是滑动窗口思想Go-Back-N 是窗口内如果有一个包丢失就回退重传后面所有包Selective Repeat 是只重传丢失的那一个。两者的差别在于对窗口内错误包的处理粒度。这个场景和算法题里“窗口移动”最像的地方在于你永远只关注窗口内这一段数据的状态窗口外的数据要么是过去式要么是未来式。4.2 服务端限流里的滑窗从固定窗口到滑动窗口后端做接口限流时最朴素的做法是固定窗口1秒内最多100次请求超过就拒绝。实现简单但有一个非常经典的临界问题如果第0.9秒来了100个请求第1.1秒又来了100个请求这两个时段各自都“合法”可实际上在0.2秒内打进来了200个请求——限流形同虚设。滑动窗口限流就是让窗口随时间平滑滚动维护最近一个时间窗口比如最近1秒的请求记录新请求进来时先把窗口外的旧请求弹出再判断当前窗口内计数是否达到阈值。用代码实现就是一套很熟悉的滑动窗口模板from collections import deque import time class SlidingWindowLimiter: def __init__(self, max_requests: int, window_seconds: float): self.max_requests max_requests self.window_seconds window_seconds self.requests deque() def allow(self) - bool: now time.time() # 弹出窗口外的旧请求 while self.requests and now - self.requests[0] self.window_seconds: self.requests.popleft() if len(self.requests) self.max_requests: self.requests.append(now) return True return False这段代码的思想和 LeetCode 209 几乎一模一样右端是当前请求时刻左端是过期请求收缩条件是“是否已经超出时间窗口”。算法题里的技巧直接平移到了生产环境。4.3 信号处理中的滑窗滑动窗口滤波怎么做信号处理里最常用的平滑手段之一就是滑动窗口滤波也叫移动平均滤波。传感器采集到的信号往往夹杂着高频噪声工程上最简单的处理是取最近 N 个样本的平均值作为输出y[n] (x[n] x[n-1] ... x[n-N1]) / N每来一个新样本窗口就往前滑动一格。这个公式和第一题的子数组和几乎相同只是用途从“求最大”变成了“求平均/去噪”。既然有和就有递推关系y_new y_old (x_new - x_old) / N只需要一次加法和一次除法就能更新滑动窗口的平均值不用重新加 N 个数。这在资源受限的嵌入式设备上非常宝贵。窗口大小 N 的选择是个典型权衡N 太小平滑效果差噪声压不住N 太大输出平滑了但响应变慢滞后明显。这就是热搜词里“滑动窗口滤波器延迟”的来源——滑动窗口滤波对输入的响应会有约 (N-1)/2 个采样周期的额外延迟窗口越长延迟越大。面试被问到“为什么移动平均会有延迟”答出这一点就够了。如果在 FPGA 里做滑动窗口滤波常见做法是移位寄存器存 N 个最新样本配合一个累加器每来一个新时钟数据移出、新数据移入累加器做一次“加新减旧”就得到新的和再除以 N 得到均值。这本质上就是把算法题的“一进一出”落到了硬件流水线上。热搜词“滑动窗口滤波verilog”指的就是这个实现思路。def moving_average(data: list[float], window_size: int) - list[float]: if len(data) window_size: return [] avg sum(data[:window_size]) / window_size result [avg] for i in range(window_size, len(data)): # 递推新均值 旧均值 (新样本 - 旧样本) / N avg (data[i] - data[i - window_size]) / window_size result.append(avg) return result5. 集训第十六天的个人经验易错点与刷题路线到了集训后半段我觉得比“会写模板”更重要的是“知道哪里会写错”。滑动窗口的代码量不大但细节非常密集一个操作顺序不对结果就全乱。这里把我踩过的坑和验证过的刷题路线一并写出来。5.1 最容易踩的四个坑第一个坑左指针移动时机搞错。固定窗口是先加右边、再判断是否需要删左边可变窗口求最短时是用 while 持续收缩。很多新手把 while 写成 if收缩不彻底答案偏大。比如 LeetCode 209如果只用 if窗口可能收缩一次就停算出来的最短长度往往不对。第二个坑辅助变量没同步。用 sum、count、set 记录窗口内容时每次 left/right 移动都必须同步更新辅助变量。漏掉 remove 的后果是窗口里有“幽灵元素”答案全错。我见过不少人调了半小时 bug最后发现问题就是 set 里忘了 remove。第三个坑死循环。左指针可能越过右指针尤其在使用 while 收缩时。要保证 left 始终小于等于 right并且注意题目的边界条件比如 LeetCode 209 中 nums 全是正数才能保证 while 一定收敛如果 target 0要单独处理。第四个坑窗口还没成型就开始记录答案。固定长度窗口必须等 right - left 1 k 时才记录。很多人喜欢用 i k 判断但窗口内容是从 i-k1 到 i下标容易差一位。建议统一用 right - left 1 这个判定一眼就能看出来窗口是否成型。分享一个我自己最常用的调试方法把每步移动后的 left、right、window_sum 或队列内容打印出来肉眼跑几轮问题基本就暴露了。滑动窗口的 bug 是典型的“看得见的 bug”打印比死盯代码高效得多。5.2 滑动窗口刷题路线从入门到进阶以下是我自己训练时验证过的顺序从固定窗口到可变窗口再到带辅助结构的窗口难度平缓上升阶段题目考察点入门LeetCode 643 子数组最大平均数 I固定窗口求和入门LeetCode 3 无重复字符的最长子串可变窗口 set入门LeetCode 209 长度最小的子数组可变窗口求最短进阶LeetCode 438 找到字符串中所有字母异位词固定窗口 计数数组进阶LeetCode 567 字符串的排列固定窗口 计数数组进阶LeetCode 239 滑动窗口最大值单调队列进阶LeetCode 76 最小覆盖子串可变窗口 哈希记账提高LeetCode 424 替换后的最长重复字符窗口内众数维护提高LeetCode 992 K个不同整数的子数组恰好K个 atMost(K) - atMost(K-1)提高LeetCode 480 滑动窗口中位数滑窗 双堆 / 有序结构每道题建议先别急着写码用手在纸上推一遍窗口移动过程。尤其是 239 这种单调队列题手推两遍之后你才能真正理解为什么队尾要弹出“老且小”的元素。5.3 第十六天集训的最后体会第十六天那天晚上我把 LeetCode 239 的单调队列代码关了屏幕默写写错了三遍才完全记住每个操作背后的“为什么”。这件事给我的触动挺大滑动窗口的模板不难背难的是理解每个操作出现的时机。对我个人来说最有效的方法是把窗口移动想象成一条流水线——右边进一个零件左边出一件成品中间的工位状态必须在一进一出之间保持一致。最后分享一个我一直沿用的技巧遇到滑动窗口题先问自己三个问题。第一窗口是固定长度还是可变长度第二辅助变量要不要支持快速最值或者需要记录计数第三答案在什么时候记录是每次移动后还是收缩完成后把这三个问题答清楚代码基本就出来了。这就是我第十六天集训沉淀下来的最核心的东西。