1. 先搞清楚滑动窗口到底在解决什么问题1.1 暴力解法为什么会超时集训进行到第16天前面已经刷过数组、链表、哈希表这些基础结构今天轮到滑动窗口。说实话这个算法第一次接触时我看了半天没想明白不就是两个指针在数组上挪来挪去吗至于被吹得这么神后来自己动手跑了一遍暴力解法才真正理解了它的价值。拿最经典的场景举例有一个长度为 n 的数组要求计算出所有长度为 k 的连续子数组的最大值。如果用暴力的写法就是从第 0 个位置开始每个位置都遍历后面 k 个元素找最大值总时间复杂度是 O(n x k)。当 n 和 k 都到了十万级别这个复杂度直接就是十亿次运算很多题目的时限只有一两秒暴力解法必挂。再换一个场景给定一个数组和一个目标值 s要求找出和大于等于 s 的最短连续子数组。暴力解法就是枚举所有起点和终点把所有连续子数组全部尝试一遍组合数是 O(n^2)。实际测试下来一万个元素的数组用暴力方案跑已经能明显感觉到卡顿五万个元素基本就等不出结果了。这正是滑动窗口要解决的问题——它把这类问题的复杂度从 O(n^2) 或 O(n x k) 直接压到 O(n)。1.2 窗口的滑动到底滑掉了什么滑动窗口的核心思想听起来其实非常朴素维护一个区间然后让这个区间像窗户一样在数据结构上从左往右滑。每滑动一步右边进来一个新元素左边出去一个旧元素窗口里的状态不需要全部重新计算只需要增量更新。这里面最关键的一条也是很多初学者最容易忽略的一条——窗口之所以能滑前提是计算的状态具有叠加性。说白了就是去掉左边离开的元素、加入右边新来的元素两步操作就能得到新窗口的状态而不需要重新扫描整个窗口。我举个例子你就明白了。假设我们要算长度为 3 的连续子数组的和初始窗口是 [1, 3, 5]和是 9。下一步窗口变成 [3, 5, 2]如果重新算一遍是 3 5 2 10需要加两次。但用滑动窗口的思路直接用 9 - 1 2 10一次减法和一次加法就完了。当窗口长度 k 很大时这个差异就是 O(k) 和 O(1) 的区别累积起来就是 O(nk) 和 O(n) 的区别。有些人可能会问那窗口里的最大值怎么办最大值这个状态可没法直接减去旧值、加上新值得到。这个问题问得很好它背后的解法是单调队列我后面在题型拆解部分会专门讲。这里先建立认知滑动窗口不是一个具体的函数而是一套通过状态复用避免重复计算的思路框架。1.3 定长窗口和变长窗口到底啥时候用哪个很多人刷滑动窗口题目时会遇到一个困惑有的题窗口大小是固定的比如长度 k 的子数组最大和有的题窗口大小是变化的比如最短子数组满足某种条件。这两种情况统称滑动窗口但处理方式是有区别的。定长窗口的写法比较简单窗口左右边界都从 0 出发右边界先走 k 步建立第一个窗口然后左右边界同步每次走一步窗口大小始终保持为 k每一步做完一次状态更新和结果记录。这种模式适合连续区间长度固定的问题比如求固定长度子串的最大平均值、统计固定窗口内不同字符的数量。变长窗口的写法通常也叫双指针或尺取法右指针负责扩张找到可行解左指针负责收缩在保证仍然可行的前提下把窗口压到最短。这种模式适合子数组连续且要满足某个条件的问题比如满足和大于等于目标的最短子数组、包含所有目标字符的最短子串。变长窗口比定长窗口稍微难一点难在收缩的时机判断——什么时候收、收到什么程度这两件事搞错了代码基本就是错的。一句话总结看到连续子数组/子串加固定长度优先想定长窗口看到连续加最短/最长/满足条件优先想变长窗口。这个判断做对了题目至少能确定大方向。2. 手写滑动窗口核心模板2.1 先讲思路扩张、维护、收缩三步法我在集训日记里反复强调一件事算法题想不清楚就先把模板写出来模板不要求覆盖所有细节但必须能把主流程立住。滑动窗口的模板我用的是三步法绝大多数题目都能套进去。第一步扩张右指针不断右移把新元素纳入窗口同时更新窗口的状态信息和、计数、频次、乘积等等。扩张的目的是寻找可行解——窗口里已经有足够的信息去满足题目的约束条件。第二步维护每移动一次右指针窗口状态就变了要么检查是否满足条件要么记录当前窗口对应的结果。这一步写得好不好决定了代码是否清晰。第三步收缩当窗口满足条件后左指针开始右移把元素从窗口中拿出同时更新状态。收缩的目的是寻找最优解——因为我们要的是最短的、最小的、或者最符合条件的滑动窗口。定长窗口严格来说没有收缩这一步因为窗口大小固定左右指针是同步移动的。但变长窗口的收缩是灵魂收缩的时机错了哪怕后面代码写得再漂亮也没用。2.2 以 Python 为例的核心模板代码我平时刷题用的语言是 Python模板代码基本长这样# 变长窗口找满足条件的最短子数组/子串 def sliding_window(s): n len(s) left 0 state {} # 窗口内的状态可以是计数、频次、集合等 result float(inf) # 初始化答案为无穷大 for right in range(n): # 第一步扩张把 s[right] 加入窗口并更新状态 # 例如state[s[right]] state.get(s[right], 0) 1 # 第二步维护/收缩——当窗口满足条件时尝试收缩 while 窗口满足题目条件: # 记录当前窗口长度 result min(result, right - left 1) # 第三步左指针右移把 s[left] 移出窗口并更新状态 # 例如state[s[left]] - 1 left 1 return result if result ! float(inf) else 0 # 定长窗口固定窗口大小 k求窗口内某种状态的最值/统计 def fixed_window(arr, k): n len(arr) left 0 state 0 # 可以是和、计数等 result [] # 先建立第一个窗口 [0, k-1] for i in range(min(k, n)): state arr[i] # 按照题目要求更新状态 result.append(state) for right in range(k, n): # 窗口变为 [left1, right] state arr[right] # 右边界进 state - arr[left] # 左边界出 left 1 result.append(state) return result这里有个很重要的细节变长窗口里的while和定长窗口里的for循环它们的作用完全不同。变长窗口的while是只要满足条件就收缩注意是while不是if因为左指针可能连续收缩多次才能达到最优——比如最小覆盖子串这类题收缩一次之后窗口可能仍然满足条件那就要继续收缩用if就只收了一个元素答案直接错了。2.3 为什么时间复杂度是 O(n)而不是 O(n^2)很多人第一次看到双指针嵌套写法时会怀疑外层 for 循环内层 while 循环这不就是 O(n^2) 吗关键点在于左右指针各自只会往一个方向移动且每个元素最多被左指针移出一次、被右指针移入一次。整个算法执行过程中left 指针从 0 走到 nright 指针也从 0 走到 n每一步操作都是常数时间。虽然看代码像是两层循环但实际上 left 和 right 的总移动次数分别只有 n 次所以总复杂度是 O(2n)也就是 O(n)。我用一个具体例子帮大家算一笔账。假设有一个长度为 10 的数组从暴力枚举所有连续子数组的话子数组总数是 n(n1)/2 55 个每个子数组求和的平均长度是 5 次操作总操作量大约 275 次。而滑动窗口方案中left 移动不超过 10 次right 移动不超过 10 次每次移动做常数操作总共不超过 20 次操作。数据量越大这个差距越夸张——当 n 等于 10 万时暴力方案是 50 亿次操作量级滑动窗口只有 20 万次。所以刷题时如果听说这题必须用滑动窗口因为 O(n^2) 会超时说的就是这个意思。理解了这个时间复杂度分析你也会明白为什么滑动窗口能作为一道独立的算法考点反复出现——它是少数能让你在面试中直接说出这个优化把复杂度从平方降到了线性的算法。3. 三个经典题型手把手拆解3.1 滑动窗口最大值单调队列是正解先看 LeetCode 第 239 题滑动窗口最大值给一个数组 nums 和窗口大小 k要求输出每个窗口中的最大值。暴力思路很简单对每个窗口扫一遍找最大值复杂度 O(nk)。能不能用我前面说的增量更新思路不行——因为最大值不具备叠加性。你只知道窗口里出去了一个 5、进来了一个 8但你不知道窗口里剩下的元素是什么最大值没法直接算出来。正解是维护一个单调递减的双端队列。这个队列的队头永远是当前窗口的最大值的索引。每当右边界进入一个新元素时把队列尾部所有比它小的元素全部弹出然后把新元素从队尾入队这样队列从头到尾就是递减的。当左边界移出窗口时如果队头元素正好是移出的那个索引就把队头弹出。这个过程听起来绕实际就是把窗口里可能成为最大值的元素按从大到小的顺序排队新来的大元素会挤掉前面所有比它小的元素。为什么可以放心弹出因为那些被弹出的元素已经不可能成为最大值了——新来的元素比它们大而且比它们晚离开窗口索引更靠右。这个晚离开的直觉是单调队列正确性的关键。参考代码如下from collections import deque def maxSlidingWindow(nums, k): res [] q deque() # 存索引队列内索引对应的 nums 值单调递减 for i, v in enumerate(nums): # 维护队列的单调性弹出队尾所有比当前值小的元素 while q and nums[q[-1]] v: q.pop() q.append(i) # 队头元素已经滑出窗口范围弹出 if q[0] i - k: q.popleft() # 窗口形成后队头就是最大值 if i k - 1: res.append(nums[q[0]]) return res注意这里有个操作顺序的坑一定是先清理队尾、再入队、最后清理队头。如果先清理队头再把新元素入队可能出现新元素刚入队就被当作滑出窗口的情况。这个顺序我一开始写反过调试了半天。提示用一个窗口内只有一个元素且新元素越来越大的用例去走一遍代码你会立刻明白单调队列每一步在做什么。3.2 最小覆盖子串变长窗口的教科书题LeetCode 第 76 题最小覆盖子串算是变长窗口里最典型的题了给定两个字符串 s 和 t要求在 s 中找到包含 t 所有字符的最短子串。这题的核心思路是右指针扩张直到窗口内已经包含 t 的所有字符此时是一个可行解但未必是最短然后左指针收缩把多余字符移出窗口直到再移一个字符就不再满足条件。此时记录窗口长度和全局最优比较。然后右指针继续扩张重复这个过程。这个过程中窗口的状态需要维护一个还需要匹配的字符数变量。常见做法是用一个数组need[128]记录每个字符还缺多少个再用一个变量cnt记录还缺几种字符。当cnt 0时说明窗口已经覆盖了所有目标字符。这里分享两个实操中总结的细节第一个细节用定长数组代替哈希表。字符集最多 128 个ASCII 范围直接need [0] * 128索引就是字符的 ASCII 码速度比哈希表快不少写起来也简洁。很多内置字符计数场景都能用这个办法。第二个细节收缩时不要每一步都重新判断是否满足条件。用cnt这个计数器来判断比每次都扫描need数组快得多。收缩时如果移出的是一个目标字符且在移出之前它的需求刚好被满足那cnt就需要加一右指针扩张时同理如果某个目标字符的需求从正数变成 0cnt就减一。这个cnt的更新逻辑是整个代码最容易出错的地方我建议你单独画一张状态变化表去验证。3.3 滑动窗口中位数偏难但值得了解LeetCode 第 480 题滑动窗口中位数在滑动窗口系列里难度算是顶配了窗口大小固定为 k但窗口内数据需要动态排序每次滑动都要输出中位数。这里不能用前面提到的单调队列因为中位数不光需要最大值或最小值而是整个窗口的有序信息。一个比较经典的解法是用双堆 延迟删除把窗口分成左半部分大顶堆存较小的一半和右半部分小顶堆存较大的一半堆顶就是中位数的候选值。但窗口滑动时有些元素会被移出窗口而这些元素可能不在堆顶无法直接弹出所以要给被移出的元素打上已删除标记等到它们出现在堆顶时才真正弹出。这个技巧叫延迟删除。说实话这题在面试中出现的频率不算高但如果你遇到了能说出双堆的思路已经能拿不少分。我的建议是先把前两题练熟中位数这题理解思路即可不需要把代码背得滚瓜烂熟。毕竟滑动窗口的最大价值在于处理连续区间内的统计问题而中位数是一个相对复杂的统计维度。3.4 这三道题放在一起看的收获如果把三道题横向对比你会发现它们的难度递进其实是有规律的题目窗口类型核心数据结构难点滑动窗口最大值定长单调队列维护单调性、弹出时机最小覆盖子串变长计数数组 计数器收缩边界判断滑动窗口中位数定长双堆 延迟删除删除非堆顶元素从这张表能看出滑动窗口的变体本质上是窗口怎么维护状态的问题。窗口里的状态如果是简单的数值和、差直接维护一个变量如果是频次或覆盖情况用计数数组如果是极值用单调队列如果是中位数或分位数就要用更复杂的堆结构。理解了这层映射关系不光是这三道题后面遇到其他滑动窗口的变体题你也能快速定位到正确解法。4. 滑动窗口不止用在算法题里4.1 信号处理中最常见的滑动窗口滤波很多人觉得滑动窗口只是刷题用的这是最大的误解。信号处理领域的滑动窗口滤波本质上就是一个滑动窗口算法。最典型的例子是均值滤波把一个长度为 N 的信号序列依次取连续的 k 个点求平均作为当前时刻的滤波输出。这跟前面讲的固定窗口和是同一个数学结构。设原始信号为 x[n]滤波后的信号 y[n] (x[n] x[n-1] ... x[n-k1]) / k。如果直接按这个公式算每个输出点要做 k 次加法但用滑动窗口的思路y[n] y[n-1] (x[n] - x[n-k]) / k每个输出点只需要一次加法和一次除法。对于高频信号处理系统这个优化能显著降低计算延迟和资源占用。工程上还有一个概念叫滑动窗口滤波器的延迟。因为第 n 个输出实际用的是从 n-k1 到 n 这一段数据输出相对当前输入有一个固定的延迟延迟大约为 (k-1)/2 个采样周期也叫群延迟。在设计实时控制系统时这个延迟不能忽略你可能需要根据系统的实时性要求反推窗口宽度 k 的取值——窗口越宽滤波越平滑但延迟越大。这是一对典型矛盾我们在做传感器数据平滑时几乎每次都要纠结这个。另外我见过有人用 Verilog 在 FPGA 上实现滑动窗口滤波思路就是维护一个移位寄存器组相当于窗口每个时钟周期移入一个新采样、移出最旧的采样同时用加法树计算窗口内所有值的和。这种硬件实现方式把滑动变成了并行的寄存器移位非常直观。4.2 时间序列预测里的窗口特征机器学习领域里滑动窗口更是无处不在。比如你看到热搜里有把企业基础采购材料、包装、能源等因子结合算法得到预测产品销售额这句话这背后就是一个典型的窗口特征构造思路。想用历史数据预测未来销售额你不能直接把一整年的数据丢给模型。常见做法是设定一个窗口大小比如过去 30 天用窗口内的销售数据、采购成本、包装费用、能源价格等因子作为模型输入预测窗口结束之后某一天或未来一段时间的销售额。这个窗口就是用近期数据反映当前状态的假设——模型认为未来一段时间的走势主要由最近的这组特征决定太久远的数据对预测的贡献可以忽略。窗口大小怎么选这其实没有标准答案。我用过的经验做法是先按业务周期试几个候选值7 天、14 天、30 天分别做交叉验证对比验证集误差。注意窗口也不是越大越好窗口太大会引入过多噪声太小则信息不足。滑动窗口在预测场景里不只是取一段数据还包括窗口滑动步长——比如每天滑动一天、生成训练样本还是每周滑动一次、生成周粒度样本。步长直接影响样本数量也影响模型训练时长要提前想好。4.3 实时统计与限流场景后端开发里有一个经典场景是接口限流。比如要求接口每秒钟最多处理 100 个请求最简单的实现就是用一个滑动窗口记录当前这一秒内的请求数新请求到来时把当前时间加入窗口同时把所有落在当前时间窗口之外的历史记录全部移除然后判断窗口内记录数是否超过阈值。这个做法相比固定窗口只判断当前秒内计数的优势是平滑。固定窗口在秒与秒的边界处容易出现双倍流量穿透的问题——比如第 59 秒来了 100 个请求、第 60 秒整点又来了 100 个请求固定窗口会认为两秒各 100 个都没超但实际上 1 秒到 2 秒之间的 200 毫秒内进来了 200 个请求。滑动窗口把时间切成更细的格子能明显缓解这种边界穿透。这也是一种定长滑动窗口的应用只是窗口里不是数值求和而是请求计数。我在实际项目中就调过一个分布式限流组件底层用的就是滑动窗口 Redis 的 ZSET 计数每个请求的时间戳作为 memberscore 也取时间戳当窗口滑动时用 ZREMRANGEBYSCORE 删掉窗口外的记录。这个方案在小型业务下实测很稳而且代码量不多。4.4 从刷题到工程的桥梁总结一下滑动窗口在不同场景下的形态其实是一致的一个连续区间、一个移动步长、一个区间状态。刷题时你关心的是时间复杂度工程中你关心的是延迟和吞吐但核心的复用区间状态思想是相通的。所以我一直认为滑动窗口是最值得花时间练熟的算法之一因为它不是纯粹的智力游戏而是可以直接落到实际系统的思路。你在 LeetCode 上把它练熟了以后再看到滑动窗口滤波滑动窗口中位数滑动窗口限流这些词就会觉得它们其实是一套东西只不过穿上了不同的行业外衣。5. 集训过程中踩过的坑和排查心得5.1 边界条件永远差 1滑动窗口题目里最常出错的不是思路而是下标。窗口长度的计算定长窗口是right - left 1绝大多数人都知道但面试手写时一紧张就写成right - left。排查这种问题有一个很笨但很有效的方法找一个长度为 3 的数组窗口大小为 2自己在纸上走一遍把 left 和 right 每步的取值写下来立刻就能发现公式对不对。另一个常见边界是窗口是否形成的判断。定长窗口里通常用if right k - 1来判断当前窗口长度是否已经达到 k变长窗口里收缩循环的结束条件往往是窗口不再满足题目要求这个条件要精确到等号算满足还是不满足。比如大于等于目标值的问题收缩到等于目标值时应该停再收就小于目标值了。这里的等号归属写错了答案就偏了。5.2 收缩的时机和收缩的量我见过不少同学写变长窗口时收缩循环用的是if而不是while导致窗口只收缩了一次就退出答案明显偏大。也有反过来的情况不该用while的地方用了while比如定长窗口题里试图收缩窗口结果把窗口大小改掉了代码完全混乱。这里我有一个判断标准题目要求的是最短最小时收缩要尽可能多收所以用 while题目要求的是固定窗口内的统计结果时窗口大小不能变不存在收缩这个动作。另外收缩的量也不一定一次只移一个元素。有一种优化叫跳跃收缩即直接找到最合适的位置把 left 跳过去这在窗口元素是字符类时尤其常用——比如某字符在窗口内出现了多次你可以直接把 left 跳到该字符最后一次出现的位置之后。5.3 状态更新顺序的坑滑动窗口最怕的就是状态更新顺序错乱。以最小覆盖子串为例当右指针扩张时是先更新计数再更新cnt还是先用cnt判断再更新计数顺序不同结果完全不同。我建议你在写代码之前把每个分支的状态变化用文字写清楚。比如如果当前字符是需要覆盖的字符并且它的需求计数在加入前大于 0说明这个字符的覆盖状态发生变化cnt 减一如果当前字符不是目标字符计数不加不减cnt 不变。把这种话写成注释放在代码旁边写循环逻辑的时候就不容易乱。调试时遇到过最离谱的一个 bug代码逻辑看着完全正确但need数组用的是[0] * 128处理大写字母和小写字母都没问题可测试样例里混入了中文全角字符索引直接越界。后来把数组长度改成了 256 才解决。虽然算法题里很少出现这种情况但在实际工程里处理非 ASCII 字符时得留意这个细节。5.4 极端用例必须自己造刷题平台会给你隐藏测试用例但你在本地跑的时候一定要自己准备几个极端用例空数组、空字符串很多模板函数第一步就要处理这种情况不加保护直接崩溃。窗口大小等于数组长度此时只有一个窗口滑动窗口代码应该正常返回一次结果而不是报错。窗口大小大于数组长度这种输入在某些题目里是非法的但你不提前判断就会产生负索引难排查。全部元素相同单调队列在窗口内所有元素相同时还能不能保持单调上容易出问题比如用还是作为弹出条件直接决定相同元素是否会被误删。元素单调递减/单调递增覆盖窗口最大值时这两种输入分别对应队头一直有效和队头频繁过期两种极端情况。我平时刷题习惯把这几类用例写成一个简单的测试函数每次改完代码就批量跑一遍。虽然不能保证 100% 覆盖所有 bug但至少能挡掉一大半低级错误。5.5 从看懂到写对的唯一路径集训这么多天下来我最大的感受是滑动窗口这类算法看懂思路是最简单的一步真正难的是在没有任何提示的情况下自己从题目描述里判断出这题应该用滑动窗口然后一次写对边界和状态更新逻辑。我的建议是练完模板之后不要急着刷难题。先找四五道简单的变长窗口题比如长度最小的子数组、水果成篮、无重复字符的最长子串每一道都要求自己完全闭卷写出来写完再对照别人的题解检查状态更新的顺序和边界处理。这几道题反复练到条件反射再去碰最大值的单调队列和最小覆盖子串会顺手很多。我个人在实际操作中的一个体会是滑动窗口其实是空间换时间思想的一种表现——窗口本身就是一个不断变化的小空间你在这个空间里维护的信息越多就越依赖数据结构的恰当选择。白天在 LeetCode 上练完单调队列晚上回去写传感器数据的滑动均值滤波代码突然发现两者的代码结构竟然可以对应上那一刻真有触类旁通的爽感。如果你也正好在集训建议把每一类滑动窗口题背后的状态维护方式整理成笔记这一步做完这一天的集训才算真正闭环。