滑动窗口 (Sliding Window) 完全指南：定长 / 变长 / 单调队列

滑动窗口 (Sliding Window) 完全指南：定长 / 变长 / 单调队列

处理「连续区间上的最优 / 计数 / 是否存在」类问题时，滑动窗口把暴力O(n²)里的重复扫描压成线性O(n)：
右端r只前进不回退，左端l按规则收缩，窗口[l, r)在序列上扫过一遍。
本文从定长窗口讲到变长双指针、单调队列（窗口最值），每节给出可直接套用的 C++ 模板和典型 LeetCode 题目。

1. 什么时候想到滑动窗口？

看到下面几类信号，优先往滑动窗口上靠：

• 连续子数组 / 子串，且要求长度固定或在约束下尽量长 / 尽量短
• 窗口内需要维护的某种量在扩右、缩左时容易增量更新（和、个数、最值等）
• 题目暗示「每个元素最多被访问常数次」—— 双指针扫一遍就是O(n)

若窗口内需要的信息没有单调性（例如子数组和等于k且数组含负数），往往要换前缀和 + 哈希表，而不是纯滑动窗口。定长/变长窗口与「前缀和」的区分见第 7 节。

2. 定长窗口：长度k的区间和 / 最大平均值

窗口长度固定为k：先算出[0, k)的和，再每次减去nums[l]、加上nums[r+1]，l与r同步右移。

sum_new = sum_old - nums[l] + nums[r] （窗口整体向右滑一格）

C++ 模板（区间和 / 最大平均值）：

#include<vector>#include<algorithm>// 长度 k 的子数组最大和（若题目要平均值，再除以 k）longlongmaxSumFixedWindow(conststd::vector<int>&nums,intk){longlongsum=0;for(inti=0;i<k&&i<static_cast<int>(nums.size());++i)sum+=nums[i];longlongbest=sum;for(intr=k;r<static_cast<int>(nums.size());++r){sum+=nums[r]-nums[r-k];best=std::max(best,sum);}returnbest;}

典型题：

• LeetCode 643：子数组最大平均数 I
• LeetCode 1052：爱生气的书店老板（定长 + 差量）
• LeetCode 1456：定长子串中元音的最大数目

3. 变长窗口（双指针）：「至多 / 至少」约束

通用形态：l、r初值均为0，r从0扫到n-1，先扩张r把元素纳入窗口，再视条件收缩l，使窗口满足题意。

两类经典问法：

1. 至多：例如「不同元素个数 ≤ k」的最长子数组 → 不满足时收缩l。
2. 至少：例如「包含所有必要字符」的最短子串 → 满足目标时再收缩l求最短。

模板 A —— 长度最短：正数数组，子数组和 ≥target（LeetCode 209）：

#include<vector>#include<algorithm>intminSubArrayLen(inttarget,conststd::vector<int>&nums){intn=static_cast<int>(nums.size());longlongsum=0;intl=0,ans=n+1;for(intr=0;r<n;++r){sum+=nums[r];while(sum>=target&&l<=r){ans=std::min(ans,r-l+1);sum-=nums[l++];}}returnans<=n?ans:0;}

模板 B —— 长度最长：「至多」约束（示例：最多含k种不同整数的最长子数组）：

#include<vector>#include<unordered_map>#include<algorithm>intlongestSubstringAtMostKDistinct(conststd::vector<int>&nums,intk){std::unordered_map<int,int>cnt;intl=0,ans=0,distinct=0;for(intr=0;r<static_cast<int>(nums.size());++r){intx=nums[r];if(++cnt[x]==1)++distinct;while(distinct>k&&l<=r){inty=nums[l++];if(--cnt[y]==0)--distinct;}ans=std::max(ans,r-l+1);}returnans;}// 「恰好 k 种」= longestAtMostK(k) - longestAtMostK(k-1)（需分别实现或复用同一函数）

模板 C —— 最短子串「至少」覆盖：先扩张到满足，再while可缩则缩并更新答案（LeetCode 76 的框架）。实现较长，此处略；核心是need/have计数与左端在仍满足时尽量右移。

典型题：

• LeetCode 3：无重复字符的最长子串（至多 0 重复）
• LeetCode 209：长度最小的子数组（和 ≥ target，正数数组）
• LeetCode 76：最小覆盖子串
• LeetCode 340：至多包含 K 个不同字符的最长子串
• LeetCode 992：K 个不同整数的子数组（恰好 k = atMost(k) - atMost(k-1)）

正数数组 + 和 ≥ S 的最短子数组：也可用双指针，因为扩右使和增大、缩左使和减小，具有单调性。若含负数则不能用纯滑动窗口求「和为 k」，需换前缀和 + 哈希。

4. 单调队列：窗口长度k内的最小值 / 最大值

对每个位置i，求[i-k+1, i]区间内的min/max，单次滑动均摊O(1)：

• 维护 deque，下标对应元素值单调递增（求 min）或单调递减（求 max）；
• 新元素入队前弹出队尾不满足单调性的下标；
• 若队首下标已不在窗口内则pop_front。

C++ 模板（每个窗口最大值，对应 LC 239）：

#include<vector>#include<deque>std::vector<int>maxSlidingWindow(conststd::vector<int>&nums,intk){std::deque<int>dq;// 存下标，对应 nums 值单调递减std::vector<int>ans;for(inti=0;i<static_cast<int>(nums.size());++i){while(!dq.empty()&&nums[dq.back()]<=nums[i])dq.pop_back();dq.push_back(i);if(dq.front()<=i-k)dq.pop_front();if(i>=k-1)ans.push_back(nums[dq.front()]);}returnans;}

求最小值把比较改成>=并在输出时取nums[dq.front()]即可。

典型题：

• LeetCode 239：滑动窗口最大值
• LeetCode 1438：绝对差不超过限制的最长连续子数组（定长试跑 + 单调队列维护 min/max）
• LeetCode 862：和至少为 K 的最短子数组（前缀和 + 单调队列优化，进阶）

5. 与二分 / 前缀和的配合

• 按列固定窗口：二维矩阵里对每一行做滑动统计，再组合（部分「矩形」题）。
• 前缀和 + 窗口：先算prefix[i]，窗口[l, r)的和为prefix[r] - prefix[l]，在「和约束」下移动l, r。
• Sliding window median：窗口内中位数需双堆或对顶堆，不是普通 deque（LeetCode 480）。

6. 常见坑与实现建议

1. 区间开闭：代码里统一用[l, r)左闭右开或[l, r]闭区间，与r - l、r - l + 1的长度公式对应好。
2. 空窗口 / 答案初值：求最短窗口时，若无合法方案要明确返回0或-1，不要误用INT_MAX未判断。
3. 恰好 k 与至多 k：「恰好 K 个不同字符」常用exactly(k) = atMost(k) - atMost(k-1)，避免在窗口里硬卡「恰好」导致实现繁琐。
4. 负数与和：子数组和为给定值且数组有负数 →不要假设滑动窗口和单调；用前缀和 + 哈希（见prefix_sum.md）。
5. 复杂度：双指针正确时每个端点最多移动O(n)次，整体O(n)；若内层再套一层线性查找未优化的结构，可能退化成O(n²)。

7. 与前缀和类技巧的区分（对照）

8. 一句话总结

• 定长→ 窗口整体平移，维护一个累积量或单调队列。
• 变长→ 右扩张、左收缩，用频数 / 集合判断合法性。
• 窗口最值→单调队列（下标单调 + 队首过期弹出）。
• 没有「扩右 / 缩左」的单调结构时，不要强行滑窗，改用前缀和 / 哈希等。

记住：「双指针」本质是每条边只朝一个方向走，总移动次数线性 —— 这是滑动窗口能O(n)的根本原因。

9. 推荐刷题顺序

1. 643 / 1052 / 1456（定长窗口） —— 熟悉「减左加右」。
2. 3 / 209 / 340（变长双指针） —— 至多约束与最短窗口。
3. 76（最小覆盖子串） —— 变长 + 复杂合法性判断。
4. 239（单调队列） —— 窗口最值模板。
5. 992 / 862（进阶：恰好 k、前缀和 + 单调队列） —— 与其它技巧综合。