★ FEATURED ARTICLE 滑动窗口这四个字听起来像个网络协议名词但在数组算法里它是处理连续子数组问题的利器。我刚开始刷题时一看到“连续子数组”“子串”就下意识写两重循环直到被一道中等题卡住超时才认真把滑动窗口的套路研究了一遍。这篇笔记不打算堆概念而是从暴力解法怎么一步步变成滑动窗口、固定窗口和可变窗口的模板有什么区别、最大值最小值为什么要请出单调队列再到我实际调试中踩过的坑一次性讲透。适合刚接触滑动窗口的初学者也适合已经能写代码但总在边界条件上翻车的人。1. 滑动窗口的思想从暴力到增量的优化过程1.1 什么是滑动窗口跟暴力循环比到底优化了什么滑动窗口本质上处理的是一段连续区间。假设数组 A你要找所有长度为 k 的子数组里和的最大值。最直接的想法是枚举每个起点累加连续 k 个数最后取最大值这就是暴力解法。对于长度为 n 的数组有大约 n-k1 个起点每个起点累加 k 个数总时间复杂度是 O(nk)当 n 到 10 的 5 次方量级时基本跑不动。滑动窗口的思路是窗口就是当前关心的那一段子数组左边界和右边界像两个游标右边界每次往右移动一格左边界也跟着移动保证窗口长度始终是 k。关键操作不是重新累加整个窗口而是利用上一次的累加结果新窗口的和等于旧窗口的和加上新进入的元素再减去离开窗口的元素。这样一次滑动只做常数次加减整体复杂度降到 O(n)。这就好比统计排队人数你不需要每次都从队头数到队尾只需要记住上一个人数来一个人加一走一个人减一。数组问题里的窗口就是为了把这种“增量更新”变成可能。1.2 判断一道题能不能用滑动窗口的三个信号不是所有数组题都能套滑动窗口我总结出三个比较靠谱的信号。第一问题要求的是连续子数组或子串。滑动窗口的区间天然连续如果题目允许跳过元素重新组合比如找子序列那窗口就不适用。第二窗口的状态可以增量维护。常见状态是区间和、区间乘积、区间内不同字符个数、区间内最大值等。这些状态都能在窗口移动时以 O(1) 或 O(log n) 的代价更新。如果每次移动窗口都需要重新计算整个区间那滑窗就没意义。第三窗口的移动路径是单向的。右边界一直往右左边界也一直往右不会大幅回退。这样每个元素最多进窗口一次、出窗口一次才能保证 O(n) 的总复杂度。像是需要在数组里反复回溯、跳跃的问题比如需要枚举所有符合某个条件的组合就不要再硬套滑动窗口了。1.3 窗口状态如何维护左右边界与更新逻辑滑动窗口代码最核心的是两个边界变量我习惯分别叫 left 和 right。right 负责扩张窗口left 负责收缩窗口。状态变量则根据题目定义比如 cur_sum、cur_product、valid_count 之类。固定长度窗口的维护逻辑比较单纯right 每移动一步就把 nums[right] 加进窗口状态同时把离开窗口的元素从状态中减掉。离开窗口的索引是 right-k不是随便拿一个 left因为窗口长度固定时left 和 right 的关系也是固定的。可变长度窗口则更像一把可以伸缩的尺子。right 不断右移扩张直到当前窗口不满足条件这时进入 while 循环left 不断右移收缩直到窗口重新满足条件。在收缩过程中每移动一次 left都要同步更新状态变量并且在合适时机记录答案。这个“先扩张后收缩”的顺序是滑窗的标准节奏很多边界错误都出在这个顺序上。2. 三种常用窗口模板与代码结构2.1 固定长度窗口模板先初始化窗口再滑动固定长度的场景很常见比如“长度为 k 的子数组最大平均值”“长度为 k 的连续子数组最大和”。这类题有一个标准模板先计算前 k 个元素的状态然后从下标 k 开始滑动。def max_sum_fixed(nums, k): if len(nums) k: return None cur sum(nums[:k]) ans cur for right in range(k, len(nums)): cur nums[right] # 新元素进窗口 cur - nums[right - k] # 旧元素出窗口 ans max(ans, cur) return ans这里有一个很重要的细节出窗口的元素索引为什么是right - k而不是另起一个变量 left因为窗口始终覆盖[right-k1, right]这一段长度刚好是 k。当 right 前进到 k 时窗口是[1, k]离开的是下标 0当 right 是 k1 时窗口是[2, k1]离开的是下标 1。这个规律用right - k直接算出省一个变量也减少出错概率。初始化时用sum(nums[:k])没问题因为它只执行一次。如果每次滑动都重新用sum或切片求和那复杂度又回到 O(nk)窗口白做了。这也是很多初学者写着写着又超时的原因。2.2 可变长度窗口模板满足/不满足条件的伸缩逻辑另一大类问题是“找满足条件的最短子数组”“最长不重复子串”等。可变长度窗口的模板和固定窗口不太一样因为窗口长度不是定死的需要根据条件动态调整左边界。以“长度最小的连续子数组其和大于等于 target”为例def min_subarray_len(target, nums): left 0 cur 0 ans float(inf) for right, val in enumerate(nums): cur val while cur target: ans min(ans, right - left 1) cur - nums[left] left 1 return ans if ans ! float(inf) else 0这个 while 内部有一个容易忽略的细节先记录答案再收缩窗口。因为收缩前的窗口刚好满足“和大于等于 target”长度可能就是当前最优候选。如果先收缩再记录就会漏掉那些长度更短的合法窗口。收缩到什么时候停止当窗口不再满足条件时也就是 cur 小于 target 时。此时 cur 可能仍然很大只是不满足题目设定的门槛。整个过程中 right 只遍历数组一次left 也最多遍历一次所以是 O(n)。2.3 基于单调队列的窗口极值模板最大值和最小值都能用固定窗口和可变窗口处理“和”“乘积”“计数”这类可加减的状态很顺手但如果题目问的是“每个长度为 k 的窗口里的最大值”普通状态变量就没法维护了。因为从窗口中移除一个元素后剩下元素的最大值不一定是已知的可能需要重新扫描。这时要引入单调队列。单调队列的思路是维护一个从队首到队尾单调递减的下标队列。新元素进队前先把队尾所有小于等于它的元素弹出去再把新元素下标放进队尾。这样队首永远是当前窗口的最大值下标。求最小值时反过来维护单调递增队列。from collections import deque def max_sliding_window(nums, k): q deque() res [] 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这个模板里我踩过的坑是过期判断为什么是q[0] i - k而不是因为窗口覆盖范围是[i-k1, i]下标等于i-k的元素已经不在窗口内必须移除。如果你写成队首刚好等于i-k时不会被清掉得到的结果就会包含窗口外元素。2.4 模板记忆与复杂度对照我整理了一个小对照表方便做题时快速确认该用哪个模板。场景窗口长度是否固定核心数据结构时间复杂度最大子数组和、固定长度均值固定左右指针 状态变量O(n)最短子数组、最长不重复子串可变左右指针 状态变量O(n)滑动窗口最大值/最小值固定或可变左右指针 双端队列O(n)三个模板的共同点都是每个元素最多被加入和移除一次。所以不管代码看起来有多长的 while总操作次数都是 O(n)。这一点也是面试时讲复杂度的重要依据。3. 实战拆解最大值、最小值、子数组统计3.1 滑动窗口最大值单调队列完整演示“滑动窗口最大值”是最经典的极值类问题。直接做的话每个窗口扫一遍找最大值时间复杂度 O(nk)。用单调队列后每个元素进出队列一次总时间 O(n)。我再用一个小例子演示单调队列的工作过程。设数组是[1, 3, -1, -3, 5, 3, 6, 7]k3。i0队列空入队 0对应值 1。i1nums[1]3弹出队尾下标 0入队 1。队列里只有值 3。i2nums[2]-1不弹直接入队。队列为[1, 2]对应值[3, -1]。当前窗口[0,1,2]最大值是 3。i3nums[3]-3入队。队列为[1,2,3]。此时队首下标 1 在窗口内输出 3。i4nums[4]5弹出所有小于 5 的队尾队列变空入队 4。输出 5。继续走完输出为[3, 3, 5, 5, 6, 7]。可以看到单调队列里的元素不一定是当前窗口的所有元素而是保持单调性的一个候选序列。队首即使不是窗口内最大值的下标也会在后续滑动中自动被淘汰。3.2 滑动窗口最小值完全对称的另一面求最小值不是新模型只要把单调队列的单调性反过来维护从队首到队尾单调递增的队列。新元素进队前弹出所有大于等于它的队尾。队首自然就是当前窗口的最小值。写代码时建议别复制粘贴后只改一个符号因为比较方向、弹出条件、命名都要跟着改。比如求最大值时是nums[q[-1]] v就弹出求最小值时是nums[q[-1]] v就弹出。这俩条件很容易写反我建议先在纸上写清楚队列里存的到底是谁的候选再去翻译成代码。这里有个实战经验如果题目要求同时输出最大值和最小值比如某些统计题可以分别用两个双端队列在一个循环里同步维护。不要做两次独立的滑动遍历虽然复杂度依然是 O(n)但多了一次无谓的空间和时间开销。3.3 子数组数量统计乘积小于 K 的滑动窗口滑动窗口不仅用来求最值还经常用来统计满足条件的子数组数量。看一个典型题给定正整数数组 nums 和整数 k统计所有连续子数组中乘积小于 k 的个数。def num_subarray_product_less_than_k(nums, k): if k 1: return 0 left 0 prod 1 ans 0 for right, v in enumerate(nums): prod * v while prod k: prod // nums[left] left 1 ans right - left 1 return ans这段代码最有意思的是最后那行ans right - left 1。为什么不是把每个可能的子数组枚举一遍因为每次进循环后当前窗口[left, right]的乘积小于 k窗口内的任意一个以 right 结尾的连续子数组乘积也都小于 k。这些子数组的右端点都是 right左端点可以从 left 一直取到 right一共right - left 1个。于是每移动一次右指针就能一次性统计所有以它为结尾的合法子数组。这也是滑动窗口在统计类题目中的核心思路不枚举子数组而是枚举右端点用窗口长度直接计算贡献。3.4 窗口内数组操作初始化、切片与状态变量的选择写窗口代码时数组基础能力经常决定代码质量。初始化方面Python 里[0] * k创建定长数组非常快JS 里new Array(k).fill(0)要注意如果填充的是对象所有元素会引用同一个对象这个坑我在用二维数组做窗口计数时踩过。切片是另一个需要警惕的操作。Python 的nums[left:right]会生成一个新的列表如果把这个操作放在循环里那么每次滑动都要复制一个子数组复杂度变成 O(n*k)内存开销也大。窗口算法真正需要的是“在原始数组上通过下标访问”而不是拷贝。同理JS 的slice方法也会复制不要在窗口循环里滥用。如果你用 VBA 或 Excel 处理数组最忌讳的是在单元格区域里反复读写正确做法是把区域一次性读进内存数组在内存里完成窗口计算后再一次性写回。这一点我在处理大量表格数据时深有体会和算法题里的“别在循环里切片”是同一个道理。4. 窗口实现中的数组细节与语言差异4.1 动态数组与索引陷阱负数下标和越界问题滑动窗口代码里下标计算是出错的重灾区。Python 的负数下标尤其会坑人比如nums[-k]在 k 很大时可能表示的并不是你想的那个位置。如果你在窗口边界判断时写了类似left-k的表达式一旦计算出负值Python 不会报错而是悄悄访问倒数第几个元素这会导致结果完全错误而程序不崩溃特别难排查。C 的 vector 则相反访问越界是未定义行为可能会直接崩溃。所以写 C 时我在进入循环前一定会先判断nums.size()和 k 的关系。JS 数组越界访问会得到 undefined参与运算后变成 NaN也不会立刻报错。不同语言的失败方式不一样但预防办法是同一个在涉及窗口边界的代码里多写显式条件不要依赖语言兜底。4.2 动态扩容数组与窗口滑动的关系有些场景下原始数据不是一次性给全的而是源源不断产生比如实时数据流。这时滑动窗口可以工作在动态数组上新数据到达时right 继续加一left 按照规则收缩。如果数据量不确定可以做动态扩容但要注意扩容本身会复制整个数组频繁扩容会拖累性能。一个更合适的做法是使用环形缓冲区或双端队列来存储流数据只保留窗口范围内的元素。这样无论数据流多长内存开销都只跟窗口大小有关。这种思路在信号处理里叫滑动窗口滤波在协议里叫滑动窗口重传核心都是同一套窗口思想只关心当前这一段数据丢掉窗口外的东西。4.3 不同语言实现滑窗的注意点Python 里实现单调队列我建议直接用collections.deque不要在 list 上用 pop(0)因为 delete 头部是 O(n) 操作。JS 里没有原生双端队列一般用数组模拟但要注意shift()也是 O(n)数据量大的时候可以用维护头指针的方式模拟队列或者用两个数组手写一个队列。C 的deque是现成的操作都是 O(1)。写 C 时还有一个性能细节尽量用nums[index]而不是nums.at(index)前者不做边界检查后者每次都会检查在窗口场景里没必要付出这个额外成本。当然这属于压榨性能的偏门技巧面试时讲清楚思路比这个重要得多。5. 常见问题、调试技巧与避坑实录5.1 边界与循环顺序错误窗口大小失控我写滑窗最常遇到的错误是窗口大小不稳定。固定窗口场景里如果在循环内同时用 left 和 right 两个变量更新但没有维护好两者的关系窗口大小就会在某一轮变成 k1 甚至 k-1。排查方法很简单在循环里打印left, right, right-left1然后和期望的窗口长度核对。如果发现窗口长度不对第一反应不是调打印而是检查 left 是不是真的只移动了一步或者出窗口时是否用了正确的索引。另一个顺序问题是可变窗口里“先收缩后记录”还是“先记录后收缩”。前面 2.2 已经说过必须先判断条件满足记录答案然后再移动 left。因为移动 left 的目的是让当前窗口不满足条件错过记录就是错过正确答案。5.2 单调队列的三个高频坑第一个坑是队尾比较时用还是。求最大值时新元素等于队尾时弹出队尾留新元素有利于淘汰更靠左的旧元素。如果你不弹结果一般也对但队列可能堆积很多重复值的下标内存会略大。我建议统一用因为代码简洁且不会出错。第二个坑是窗口未形成时不能输出结果。在循环for i中只要i k-1才说明当前位置已经凑够一个窗口。很多新手把输出条件写成if i k就会漏掉第一个窗口。第三个坑是过期判断使用下标而不是值。队列里如果直接存值你无法知道一个值当前是不是还在窗口里因为可能存在重复元素。存下标后任何时刻都可以用q[0] i - k判断队首是否过期这是单调队列题目里的标准做法。5.3 性能排查为什么越优化越慢有些时候代码逻辑看着正确但提交后运行时间反而变长。我遇到过两种情况。第一种是在循环内部用了高开销操作比如 Python 的max(q)、sum(nums[left:right])、内部再开一次循环。这些操作会让“看起来是滑窗”的代码退化成 O(nk)。解决办法是把需要维护的状态用变量保存而不是每次临时计算。第二种是数据结构选择不对。比如 Python 的 list 头部弹出是 O(n)如果你用list.pop(0)实现队列外层虽然只遍历一次内层却是线性时间整体变成 O(n^2)。换成deque.popleft()才是真正的 O(1)。C 里如果只用 vector 当队列并频繁 erase(begin) 也有同样问题应改成deque或维护头指针。5.4 调试方法论先用暴力结果当基准我有一套比较笨但很有效的调试流程先写一个暴力双循环版本保证结果正确再写滑动窗口版本。然后把两个版本的结果在随机小规模数组上对比一旦不一致立刻能定位到是哪一步的状态更新出了问题。对比时不要只看最终输出要打印每一轮滑动窗口的左右边界、状态变量和窗口内容。暴力版本虽然慢但它每一步的窗口内容都是直观可见的滑动窗口版本每一轮的窗口内容应该和暴力版本完全一致。只要窗口中每个元素对上了说明边界和状态更新都没有问题。我个人在实际操作中的体会是滑动窗口不是一个背模板就能一劳永逸的东西它更是一种“用空间换时间、用增量代替重复计算”的思维习惯。每当你发现一个数组问题在循环里反复计算连续区间就可以停下来想想能不能让这些计算只发生一次如果能滑动窗口大概率就是那条路。
阅读完成 · 觉得有帮助？
