滑动窗口 · Sliding Window

很多「连续子数组 / 子串」问题,暴力写法都要枚举所有区间再逐个求值,嵌套两层循环 O(n·k) 甚至 O(n²)。但这些区间是连续滑过的 —— 相邻两个窗口大部分元素重叠,只差一进一出。抓住这点,用一个随下标单向移动的窗口、只做增量维护,就能把整个过程压成一遍 O(n) 扫描。滑动窗口不是单个算法,而是一类方法,按窗口宽度是否固定分为两大类:

其一,定长窗口:宽度固定为 k,从左滑到右。窗口右移一格只换掉一进一出两个数 —— 能增量维护的聚合 (和 / 计数) 一次加减就更新完;但最值这种不能简单增量的,需要单调队列。其二,变长窗口(毛毛虫 caterpillar):宽度由条件驱动伸缩 —— 右指针 R 扩张,左指针 L 在条件被破坏 / 已满足时收缩,L、R 都只增不减,各扫一遍。

前置知识:本系列建立在双指针 Two Pointer 的「同向双指针」流派之上 —— 变长窗口的 L / R 正是一对同向移动的指针,建议先了解该系列的总览。每页都能改输入、单步推进,观察窗口在数组 / 字符串上滑动(青色 = 当前窗口 / 左指针 / 紫色 = 右指针 / 黄色 = 至今最优窗口),旁边代码逐行点亮。

定长窗口:宽度恒为 k,出一进一

Fixed Sum · 增量更新

窗口和：出一个、进一个，不必重算

定长窗口右移一格只滑走最左、滑进最右，一次加减即可更新窗内和。这个增量更新把朴素的 $O(nk)$ 压到 $O(n)$。

Window Maximum · 朴素引子

窗内取最值：为什么不能简单「出一进一」

把聚合从「和」换成「最大值」后增量更新失效：滑走的若恰是当前最大，就得在剩下的数里重找。朴素法因此退回 $O(nk)$。

Monotonic Deque · 核心

双端单调队列：及时舍弃「不可能成为最大值」的数

比当前数小又比它早的数不可能再成为后续窗口的最大值。用双端队列维持单调递减，每个下标只进出各一次，整体 $O(n)$。

Block / Sparse Table · 旁支

分块法：按 k 切块，预处理块内前缀 / 后缀最大值

把数组每 $k$ 个切成一块，任意长 $k$ 的窗口要么整块、要么横跨相邻两块。预处理 $O(n)$、查询 $O(1)$。

变长窗口:宽度由条件驱动伸缩

Longest · 右扩左缩求最长

无重复字符的最长子串：遇到重复就把左指针跳过去

窗口宽度不再固定：右指针纳入新字符撑长窗口，出现重复就把左指针直接跳到重复字符右边。左指针绝不回退，所以是 $O(n)$。

Shortest · 达标后缩左求最短

长度最小的子数组：右扩到「达标」，再尽力缩左

求和不小于目标的最短子数组。它与「无重复最长子串」是求最短与求最长的镜像：一个还能缩时记录，一个被迫缩时记录。

落地:生产代码中的滑动窗口

applications · 真实应用

应用实例：生产代码中的滑动窗口与单调队列

用两个单调队列实时维护传感器窗口的最大最小值，把朴素的每步重扫压到均摊 $O(1)$。末节梳理流式聚合、限流计数器等同源场景。

如何选择:定长 vs 变长先看题面:窗口宽度是否给定。定长里若聚合可增量(和 / 计数)直接一减一加;若是最值就用双端单调队列(严格 O(n)、实现简单、可扩展为流式)。变长则看求最长还是最短、收缩条件是什么。三者都建立在「窗口单向滑动 + 增量维护」这同一内核上,按问题形态采取了不同形式。

🔗 相关链接

• 3. 无重复字符的最长子串 · LeetCode 变长窗口求最长的入门题,本系列「无重复字符的最长子串」页取自这里。
• 209. 长度最小的子数组 · LeetCode 变长窗口求最短的代表题,本系列「长度最小的子数组」页取自这里。
• 239. 滑动窗口最大值 · LeetCode 定长窗口取最值的经典题,本系列单调队列 / 分块两页的示例数组与 k 取自这里。
• 单调队列 · OI Wiki 单调队列的定义、滑动窗口模板,以及它在单调队列优化 DP 里的标准用法。
• Sparse Table · cp-algorithms.com 分块 / 倍增预处理静态区间最值 (RMQ) 的权威讲解,与本系列「分块法」同源。

和别的系列串起来看:变长窗口的「右扩 + 左缩」正是 双指针 Two Pointer里「同向双指针」流派最常见的落地形态;定长取最值里队尾「弹出所有比新数小的旧数」的做法,和 优先队列 / 二叉堆里「最值上浮」是一脉相承的「只留有希望的候选」;而分块法「预处理区间聚合 → 查询变成端点取值」的思路,正是 区间查询 (前缀和 / 树状数组 / 线段树)那一系列的主线。