大概半年以前我第一次在数组题里碰到滑动窗口这个概念。当时在解一道很普通的题给一个长度 n 的整数数组找长度固定为 k 的连续子数组最大和。我的第一反应是写双重循环结果在大数据量上直接超时。后来我才明白这题完全不复杂滑动窗口就是它的教科书级解法。这份笔记算是把我对“滑动窗口在数组中的应用”的完整理解整理了一遍。里面既有固定窗口和可变窗口的通用模板也有单调队列这种进阶手段还包括大量边界条件和调试经验。适合刚开始刷算法、准备技术面试或者想系统梳理这类题型的开发者参考。我会尽量少说废话直接讲清楚怎么做、为什么这么做以及容易踩的坑。1. 滑动窗口到底在解决什么问题1.1 为什么暴力循环不是好方案先看一个最经典的入手题。数组[2, 1, 5, 1, 3, 2]k 3求长度为 3 的连续子数组最大和。暴力思路很简单枚举所有可能的起始位置i再对i到i k - 1这一段求和每次求和相当于一个内层循环。这个解法的时间复杂度是O(n × k)。如果数组长度是十万窗口长度是五千那就要跑五亿次加法即使编译器做了不少优化依然会慢得让人难受。这还只是求和如果窗口内的操作不是加和而是统计频次、维护最大值、判断是否包含重复元素暴力法的代价会更高。很多初学者容易忽略的一点是暴力法的问题不只是“重复计算太多”而是它完全没有利用相邻窗口之间的重叠关系。窗口向右滑动一格中间大部分元素都没变乱算一遍太浪费了。1.2 复用它已经算好的结果滑动窗口的核心就一句话不要重新算只做增量更新。还是拿上面那个数组打比方。窗口第一次覆盖[2, 1, 5]和是 8。窗口向右移动一格后覆盖[1, 5, 1]这时发生了什么新元素1进入窗口旧元素2离开窗口中间元素1, 5保持不变。所以新窗口的和可以直接算成8 - 2 1 7。不需要再把1 5 1求一遍。这就是滑动窗口最本质的优化思路用数学关系复用已经计算的信息。窗口就像一条在数组上滑动的传送带进一个出一个中间的东西原封不动。你只需要关心“移出窗口”和“进入窗口”这两个动作其余结果都可以像滚雪球一样滚出来。这种思想在很多工程场景里也有影子比如滑动窗口滤波模型本质上就是对一个连续的采样序列维护一个固定长度窗口窗口内做均值或中位数计算每来一个新样本更新窗口内的统计值而不是把窗口内所有样本重新算一遍。算法题里的滑动窗口和它是一脉相承的。2. 固定窗口和可变窗口两类模板必须分开记2.1 固定长度窗口模板固定窗口问题有个非常标准的结构窗口长度是固定的k右指针每移动一步左指针也跟着移动一步窗口大小始终保持不变。我曾经习惯用一个基于“前缀和思想”的写法比如求最大子数组和时每次循环做window_sum nums[i] - nums[i - k]。这个写法简洁但缺点是只适用于数值求和遇到统计字符频次、维护集合等场景就不够通用了。后来我改用下面这个更通用的固定窗口模板def fixed_window(nums, k): n len(nums) if n k: return None left 0 window_sum 0 ans 0 for right in range(n): # 1. 把 nums[right] 放进窗口更新窗口数据 window_sum nums[right] # 2. 窗口长度达到 k if right - left 1 k: # 3. 记录答案比如求最大和 ans max(ans, window_sum) # 4. 移除 nums[left]窗口整体右移 window_sum - nums[left] left 1 return ans这个模板好在哪它用left和right两个指针显式地表示窗口边界所有窗口数据的更新都放在“进入窗口”和“离开窗口”两个位置无论窗口内需要维护什么信息都只需要改第 1 步和第 4 步。比如把“求最大和”换成“求长度为 k 的连续子数组的平均值”或者“求长度为 k 的窗口内不同字符个数”模板仍然成立。这个可变性是非常重要的千万不要把固定窗口代码写成只能求和的单一形式。2.2 可变窗口的通用循环结构可变窗口比固定窗口稍微难一点因为窗口长度不固定左指针不一定每一步都移动。它解决的问题通常是“求满足某种条件的最长/最短连续子数组”。最典型的一个例子给定一个字符串找出不含重复字符的最长子串的长度。这类问题用暴力法不仅慢而且容易漏情况而滑动窗口天然能覆盖所有连续区间。可变窗口的通用结构是这样的left 0 ans 0 for right in range(n): # 1. 把 nums[right] 放进窗口 # 2. 更新窗口状态比如记录字符出现次数 # 3. 当窗口不满足条件时不断移动 left 缩小窗口 while not valid(): # 把 nums[left] 移出窗口 # 更新窗口状态 left 1 # 4. 此时窗口是合法的记录答案 ans max(ans, right - left 1)关键点在第 3 步while not valid()里的判定条件决定了这个窗口是“最长”型还是“最短”型问题。以“不含重复字符的最长子串”为例def length_of_longest_substring(s: str) - int: seen set() left 0 ans 0 for right, ch in enumerate(s): while ch in seen: seen.remove(s[left]) left 1 seen.add(ch) ans max(ans, right - left 1) return ans每次遇到一个新字符如果它已经出现在当前窗口里说明窗口不合法了我们就把left往右移把重复字符移出set。直到窗口重新合法再更新答案。而“最短”型问题就是另一套逻辑比如 LeetCode 209 题“长度最小的子数组”def min_subarray_len(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 ans if ans ! float(inf) else 0仔细看最长型和最短型的区别就一句话最长型在窗口不合法时收缩在收缩后窗口合法时更新答案最短型在窗口满足条件时先更新答案再收缩。这个顺序如果搞反代码就会出错。2.3 什么时候可以用滑动窗口什么时候不能用不是所有连续子数组问题都适合滑动窗口。在我看来能用滑动窗口的问题通常满足两个隐式条件窗口的单调性随着窗口变大某个度量是单调增或单调减的。比如正整数数组的子数组和窗口越长和越大或者某个字符出现次数窗口越大越容易重复。这种单调性让“收缩”和“扩张”有了确定性方向。约束条件和子数组连续题目要求找的是连续的一段而不是子序列。滑动窗口天然把区间当作“连续的一段”来维护一旦题目改成“可以从数组中任意挑几个元素”滑动窗口就不再适用。遇到那种数组元素可正可负且要求找乘积等于某值的最短子数组之类的问题也要小心。因为负数会让乘积在增大和减小之间来回跳动窗口失去单调性滑动窗口就未必好使。这时往往要配合前缀和、哈希表甚至状态压缩来处理。3. 不同语言写滑动窗口的细节对照3.1 Python小心切片和错误的初始化Python 写滑动窗口很舒服但也有几个坑。第一个坑是数组初始化时过度使用切片。比如求窗口和有人会写sum(nums[left:right1])。虽然这种写法看着简单但切片会复制出新数组每次循环都复制一趟时间复杂度和空间复杂度都变差。窗口滑动类题目追求的是O(n)一旦引入切片性能就回归到近似O(n × k)了。第二个坑是set或字典的更新顺序。在不含重复字符的最长子串中我先判断ch in seen再往seen里添加字符。如果你先添加再去查重就会导致窗口永远认为自己合法查不出重复字符。这个顺序问题我在刚开始练习的时候犯过好几次。第三个坑是 Python 的循环变量作用域。left 1这种操作在普通函数里没问题但如果你把算法包在闭包函数里并且没写nonlocal会报变量绑定错误。虽然这个错误和算法无关但面试时遇到挺影响心态。3.2 JavaScriptMap 比 Set 更实用很多人写 JS 版滑动窗口模板时喜欢直接用Set来去重。在纯去重场景里Set没问题但一旦题目要求统计字符出现次数或者需要知道某个字符最后一次出现的位置Set就完全不够用了。比如“无重复字符的最长子串”的 JS 版本模板我个人建议直接用Map记录每个字符最近一次出现的下标function lengthOfLongestSubstring(s) { let left 0; let ans 0; const lastIndex new Map(); for (let right 0; right s.length; right) { const ch s[right]; if (lastIndex.has(ch) lastIndex.get(ch) left) { left lastIndex.get(ch) 1; } lastIndex.set(ch, right); ans Math.max(ans, right - left 1); } return ans; }这个写法比“不断 pop left 直到窗口合法”更快因为它的指针跳跃是直接完成的不需要while循环逐步移动。另一个 JS 特有的坑是数组方法的使用惯性。很多 JS 开发者习惯用map/filter/slice处理数组但在滑动窗口题里这些方法几乎都会造成额外的数组复制。窗口维护要的是改变状态不是生成新数组所以优先用原始下标操作少用不可变风格的方式。3.3 C 和 Java性能与容器选择C 选手写滑动窗口最大的优势是std::vector的下标访问几乎零成本。但要注意int溢出求窗口和时n可以到十万k还可以很大window_sum用int很可能溢出。建议直接使用long long避免在边界数据上翻车。Java 里处理窗口最值时PriorityQueue虽然能取出最大值但删除任意元素很别扭。这里我强烈建议用ArrayDeque或者LinkedList来模拟单调队列而不是用堆。Java 的PriorityQueue.remove(Object)是O(k)的在滑动窗口题目里这几乎等于把优化效果全部浪费掉。C 里还有一个小优化点右指针和左指针尽量用int而不是size_t。因为size_t是无符号类型当left - 1或者right - left 1出现负数时无符号类型会把负值变成一个很大的正数导致边界判断完全混乱。我在刷题时见过太多次这样的错误了都是一个看似无关紧要的unsigned引起的。4. 单调队列处理滑动窗口最大值和最小值4.1 为什么不能直接用堆如果说固定窗口和可变窗口是滑动窗口的第一层那单调队列就是它的进阶形态。考虑这样的场景给定数组[1, 3, -1, -3, 5, 3, 6, 7]窗口大小k 3要求输出每个窗口的最大值。暴力解法是每滑动一次就扫描窗口内所有元素求最大值复杂度O(nk)。这时有人会想到用最大堆。堆确实能在O(log k)时间内取到最大值但问题是窗口滑走以后堆顶元素可能已经不在窗口内了。你需要一种方法“惰性删除”过期元素。这个逻辑做起来很麻烦因为堆只能管最大值无法高效删除中间任意元素。所以正确方案是单调双向队列。它维护一个队列队列里的元素永远是“从队头到队尾单调递减”的。这样队头就是当前窗口最大值而且最大值一旦滑出窗口就能立刻从队头弹出。4.2 单调队列的经典模板这里我给出一份可以直接套用的 Python 版本队列里存的是数组下标而不是值from collections import deque def max_sliding_window(nums, k): q deque() res [] for i, v in enumerate(nums): # 1. 把窗口外的过期下标弹出 while q and q[0] i - k: q.popleft() # 2. 新元素从队尾入队但先把比它小的元素清掉 while q and nums[q[-1]] v: q.pop() q.append(i) # 3. 当窗口达到 k 时开始记录答案 if i k - 1: res.append(nums[q[0]]) return res这段代码的“神”在第 2 步。为什么可以放心把队尾比当前元素小的值全部丢掉因为窗口是向右滑动的这个新元素不仅更大而且更靠右也就意味着它比旧元素“存活时间更长”。任何包含旧元素作为最大值的窗口换成这个新元素都只会更好所以旧元素再也没有机会成为答案。想求窗口最小值只需要把第 2 步的改成让队列保持单调递增队头就是最小值。这种单调队列的做法对每个元素最多入队一次、出队一次整体复杂度是严格的O(n)。面试时如果碰到“滑动窗口最大值/最小值”这类题单调队列基本就是标准答案。顺便说一句在工程实现里滑动窗口滤波器也经常用类似思路。硬件上用 Verilog 实现滑动窗口滤波时往往会用一个 FIFO 队列来缓存窗口内的数据再配合比较器更新最值软件里用双端队列维护候选数据则是我个人认为最贴近硬件直觉的写法。4.3 一维之外的延伸热词里出现了“二维数组”和“多维数组指针”说明不少人在数组问题上会遇到更高维的滑动窗口。二维滑窗其实可以理解成“先在行方向做一次一维滑窗再在列方向做一次一维滑窗”。比如在一个m × n矩阵里求所有k × k子矩阵的最大值可以先对每一行求横向滑动窗口最大值得到一个m × (n - k 1)的中间结果矩阵再对中间结果矩阵的每一列做纵向滑动窗口最大值就能拿到每个k × k方块的最大值。这种“两次一维滑窗”的组合比暴力枚举所有方块快非常多。不过二维情况下的边界处理要格外小心尤其是k大于矩阵某个维度时直接返回空数组不要尝试访问非法下标。5. 实操记录常见问题、边界条件与练手建议5.1 我踩过的几个坑第一个坑是固定窗口的指针移动时机。有人习惯先把left加一再移除旧元素结果移除的下标已经变了移除错了数值。正确顺序应该是先记录答案再把left指向的元素从窗口统计里减掉最后才left 1。这个顺序我在初学时反复错过。第二个坑是可变窗口的“收缩时机”。对于最小覆盖子串这类问题收缩条件不是“窗口不合法”而是“窗口已经合法且可能更短”。这时候要先更新答案再收缩。如果反着来你会把一个合法状态的窗口收缩成不合法状态答案就丢失了。第三个坑是单调队列里存下标而不是存值。如果你存的是值当最大值滑出窗口时你根本不知道它是否已经过期最后会输出错误答案。存下标才能精确判断q[0] i - k。另外还有一个非常容易忽略的点当题目有多个约束条件时不要盲目使用while收缩。比如窗口内既要满足字符种类限制又要满足每种字符的个数限制这时收缩可能只需要针对某一个维度进行另一维会自动恢复合法。如果把所有条件都放到一个while里会导致指针过度回退。5.2 我建议的边界自测数据代码写完先不要急着提交先用几个边界数据自测。我以前吃过不少亏现在整理成一张速查表边界场景测试数据预期结果数组长度等于窗口长度[1, 2, 3], k 3最大和 6数组长度小于 k[1, 2], k 3通常返回空或 0空数组[], k 2返回空或 0窗口内包含负数[-1, -2, -3], k 2最大和 -3所有元素相等[5, 5, 5], k 2最大和 10元素极大可能溢出[200000, 300000], k 2考虑 long long无重复字符最长子串为空串0这些数据基本覆盖了最典型的边界问题。特别是负数很多人写“最大窗口和”时会默认答案初始化为 0结果遇到全负数数组直接失败。正确做法是把答案初始化为float(-inf)或数组里的第一个窗口值不要想当然地初始化为 0。5.3 三到四道值得反复做的变式题如果只让我推荐三道题来巩固滑动窗口我会推荐下面这些第一道是“长度最小的子数组”。它是最典型的可变窗口最短类题目理解了它的收缩方式就理解了最短类问题的模板。第二道是“无重复字符的最长子串”。它是最典型的最长类题目重点在于如何维护窗口内的字符状态以及什么时候该用Map什么时候该用Set。第三道是“滑动窗口最大值”。它是单调队列的入门题也是面试高频题。能把这道题的代码背熟并且讲清楚为什么队尾可以弹出元素基本就能应对这一类进阶题了。第四道可以挑战“最小覆盖子串”。这道题的难度在于窗口内要维护两套计数一套是目标串的字符需求一套是当前窗口的实际字符数。它能把你的滑动窗口掌握水平拉高一个层次。我个人在面试前通常会把这几道题的“模板骨架”默写一遍。不是死记代码而是默写每个步骤的注释进入窗口做什么、收缩做什么、记录答案在哪一步。这样无论题目怎么包装核心逻辑都不会走形。再说一个我自己的习惯写完滑动窗口代码后会在大脑里人工跑一遍窗口大小为 1 和窗口大小为整个数组的情况。因为这两种情况最容易暴露 off-by-one 错误。窗口大小为 1 时每个元素都是一个独立窗口窗口大小为整个数组时只有一次有效答案。这两头都跑通了代码基本就稳了。这个技巧帮我在好几次笔试里避免了大意失分也让我对滑动窗口的边界条件越来越敏感。希望这份笔记里的模板和踩坑记录也能帮你把“滑动窗口在数组中的应用”这一块彻底拿稳。