滑动窗口 · Sliding Window

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

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

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

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

Fixed Sum · 增量更新

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

最基础的入门题：宽 k 的窗口求窗内和 / 均值(LeetCode 643)。关键观察——窗口右移一格只滑走最左、滑进最右，中间 k-2 个数没变，所以新和 = 旧和 -出去的+进来的，一次加减就更新。这个「增量更新」是滑动窗口的核心，把朴素 O(n·k) 压到 O(n)。单步观察窗口滑动、窗内和如何一减一加地更新。

Window Maximum · 朴素引子

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

把聚合从「和」换成「最大值」(LeetCode 239)，增量更新就失效了：滑走的若恰是当前最大，新最大值无法靠一次减法算出来，得在剩下 k-1 个里重找。朴素法只能每个窗口把 k 个数从头比一遍，共 O(n·k)——这一页单步展示「重复比较」浪费在哪，引出后面两种 O(n) 解法。

Monotonic Deque · 核心

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

关键性质：扫到一个数，它前面那些比它小、又比它早的数，不可能再成为后续任何窗口的最大值。于是用一个双端队列存下标、维持值单调递减：新数从队尾把所有 ≤ 它的弹出再入队，队首永远是当前窗口最大值；队首滑出窗口就从前端弹出。每个下标只进出各一次 → 整体 O(n)。单步观察队尾淘汰、队首输出最大值、数组与队列同步高亮。

Block / Sparse Table · 旁支

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

另一条路（sparse table 的近亲）：把数组每 k 个切成一块。任意长 k 的窗口，要么是一整块、要么横跨相邻两块。预处理出每个位置到块开头的最大值 lmax 与到块结尾的最大值 rmax，窗口 [L,R] 的最大值就是 max(rmax[L], lmax[R])——左半截 + 右半截拼起来。预处理 O(n)、查询 O(1)。单步观察窗口如何被切成两截。

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

Longest · 右扩左缩求最长

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

LeetCode 3。窗口宽度不再固定：右指针 R 不断纳入新字符把窗口撑长；一旦窗内出现重复字符，就把左指针 L 跳到那个重复字符的右边，缩回「无重复」。每个 R 处的合法窗口长 R-L+1 取最大即答案。L 一步到位、绝不回退，所以是 O(n) 而非 O(n²)。单步观察毛毛虫式的「扩-缩」与左指针的跳跃。

Shortest · 达标后缩左求最短

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

LeetCode 209，目标反过来求最短：给正整数数组与 target，找和 ≥ target 的最短连续子数组。右指针纳入新数把窗口和撑到达标，就反过来缩左——在「仍达标」的前提下尽量移除左边的数，每缩一步记一次长度。和「无重复最长子串」正好是求最长 / 求最短的镜像：一个「被迫缩时记录」、一个「还能缩时记录」。单步观察窗口和的涨落与左右边界的伸缩。

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

applications · 真实应用

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

一个可动手体验的真实场景：用两个单调队列实时维护传感器数据滑动窗口的最大 / 最小值（峰谷监控、最近 k 秒极差告警），把朴素的「每步重扫 k 个」压到均摊 O(1)。再梳理滑动窗口的其他应用场景：单调队列优化 DP、流式窗口聚合（Flink / 时序数据库）、限流的滑动窗口计数器，以及一组同源 LeetCode 题 (3 / 76 / 209 / 239 / 862 / 1438)。

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

🔗 相关链接

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

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