滑动窗口算法详解：从模板到实战，双指针与单调队列全攻略

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): # 窗口变为 [left+1, 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 走到 n，right 指针也从 0 走到 n，每一步操作都是常数时间。虽然看代码像是两层循环，但实际上 left 和 right 的总移动次数分别只有 n 次，所以总复杂度是 O(2n)，也就是 O(n)。

我用一个具体例子帮大家算一笔账。假设有一个长度为 10 的数组，从暴力枚举所有连续子数组的话，子数组总数是 n(n+1)/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就需要加一；右指针扩张时同理，如果某个目标字符的需求从正数变成 0，cnt就减一。这个cnt的更新逻辑是整个代码最容易出错的地方，我建议你单独画一张状态变化表去验证。

3.3 滑动窗口中位数：偏难但值得了解

LeetCode 第 480 题"滑动窗口中位数"在滑动窗口系列里难度算是顶配了：窗口大小固定为 k，但窗口内数据需要动态排序，每次滑动都要输出中位数。

这里不能用前面提到的单调队列，因为中位数不光需要最大值或最小值，而是整个窗口的有序信息。一个比较经典的解法是用双堆 + 延迟删除：把窗口分成左半部分（大顶堆存较小的一半）和右半部分（小顶堆存较大的一半），堆顶就是中位数的候选值。但窗口滑动时有些元素会被移出窗口，而这些元素可能不在堆顶，无法直接弹出，所以要给被移出的元素打上"已删除"标记，等到它们出现在堆顶时才真正弹出。这个技巧叫延迟删除。

说实话，这题在面试中出现的频率不算高，但如果你遇到了，能说出双堆的思路已经能拿不少分。我的建议是：先把前两题练熟，中位数这题理解思路即可，不需要把代码背得滚瓜烂熟。毕竟滑动窗口的最大价值在于处理"连续区间内的统计问题"，而中位数是一个相对复杂的统计维度。

3.4 这三道题放在一起看的收获

如果把三道题横向对比，你会发现它们的难度递进其实是有规律的：

从这张表能看出，滑动窗口的变体本质上是"窗口怎么维护状态"的问题。窗口里的状态如果是简单的数值（和、差），直接维护一个变量；如果是频次或覆盖情况，用计数数组；如果是极值，用单调队列；如果是中位数或分位数，就要用更复杂的堆结构。理解了这层映射关系，不光是这三道题，后面遇到其他滑动窗口的变体题你也能快速定位到正确解法。

4. 滑动窗口不止用在算法题里

4.1 信号处理中最常见的滑动窗口滤波

很多人觉得滑动窗口只是刷题用的，这是最大的误解。信号处理领域的滑动窗口滤波，本质上就是一个滑动窗口算法。

最典型的例子是均值滤波：把一个长度为 N 的信号序列，依次取连续的 k 个点求平均，作为当前时刻的滤波输出。这跟前面讲的"固定窗口和"是同一个数学结构。设原始信号为 x[n]，滤波后的信号 y[n] = (x[n] + x[n-1] + ... + x[n-k+1]) / k。如果直接按这个公式算，每个输出点要做 k 次加法；但用滑动窗口的思路，y[n] = y[n-1] + (x[n] - x[n-k]) / k，每个输出点只需要一次加法和一次除法。对于高频信号处理系统，这个优化能显著降低计算延迟和资源占用。

工程上还有一个概念叫"滑动窗口滤波器的延迟"。因为第 n 个输出实际用的是从 n-k+1 到 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 计数：每个请求的时间戳作为 member，score 也取时间戳，当窗口滑动时用 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 上练完单调队列，晚上回去写传感器数据的滑动均值滤波代码，突然发现两者的代码结构竟然可以对应上，那一刻真有触类旁通的爽感。如果你也正好在集训，建议把每一类滑动窗口题背后的"状态维护方式"整理成笔记，这一步做完，这一天的集训才算真正闭环。