滑动窗口 (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[r1]l与r同步右移。sum_new sum_old - nums[l] nums[r] 窗口整体向右滑一格C 模板区间和 / 最大平均值#includevector#includealgorithm// 长度 k 的子数组最大和若题目要平均值再除以 klonglongmaxSumFixedWindow(conststd::vectorintnums,intk){longlongsum0;for(inti0;ikistatic_castint(nums.size());i)sumnums[i];longlongbestsum;for(intrk;rstatic_castint(nums.size());r){sumnums[r]-nums[r-k];beststd::max(best,sum);}returnbest;}典型题LeetCode 643子数组最大平均数 ILeetCode 1052爱生气的书店老板定长 差量LeetCode 1456定长子串中元音的最大数目3. 变长窗口双指针「至多 / 至少」约束通用形态l、r初值均为0r从0扫到n-1先扩张r把元素纳入窗口再视条件收缩l使窗口满足题意。两类经典问法至多例如「不同元素个数 ≤ k」的最长子数组 → 不满足时收缩l。至少例如「包含所有必要字符」的最短子串 → 满足目标时再收缩l求最短。模板 A —— 长度最短正数数组子数组和 ≥targetLeetCode 209#includevector#includealgorithmintminSubArrayLen(inttarget,conststd::vectorintnums){intnstatic_castint(nums.size());longlongsum0;intl0,ansn1;for(intr0;rn;r){sumnums[r];while(sumtargetlr){ansstd::min(ans,r-l1);sum-nums[l];}}returnansn?ans:0;}模板 B —— 长度最长「至多」约束示例最多含k种不同整数的最长子数组#includevector#includeunordered_map#includealgorithmintlongestSubstringAtMostKDistinct(conststd::vectorintnums,intk){std::unordered_mapint,intcnt;intl0,ans0,distinct0;for(intr0;rstatic_castint(nums.size());r){intxnums[r];if(cnt[x]1)distinct;while(distinctklr){intynums[l];if(--cnt[y]0)--distinct;}ansstd::max(ans,r-l1);}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 992K 个不同整数的子数组恰好 k atMost(k) - atMost(k-1)正数数组 和 ≥ S 的最短子数组也可用双指针因为扩右使和增大、缩左使和减小具有单调性。若含负数则不能用纯滑动窗口求「和为 k」需换前缀和 哈希。4. 单调队列窗口长度k内的最小值 / 最大值对每个位置i求[i-k1, i]区间内的min/max单次滑动均摊O(1)维护 deque下标对应元素值单调递增求 min或单调递减求 max新元素入队前弹出队尾不满足单调性的下标若队首下标已不在窗口内则pop_front。C 模板每个窗口最大值对应 LC 239#includevector#includedequestd::vectorintmaxSlidingWindow(conststd::vectorintnums,intk){std::dequeintdq;// 存下标对应 nums 值单调递减std::vectorintans;for(inti0;istatic_castint(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(ik-1)ans.push_back(nums[dq.front()]);}returnans;}求最小值把比较改成并在输出时取nums[dq.front()]即可。典型题LeetCode 239滑动窗口最大值LeetCode 1438绝对差不超过限制的最长连续子数组定长试跑 单调队列维护 min/maxLeetCode 862和至少为 K 的最短子数组前缀和 单调队列优化进阶5. 与二分 / 前缀和的配合按列固定窗口二维矩阵里对每一行做滑动统计再组合部分「矩形」题。前缀和 窗口先算prefix[i]窗口[l, r)的和为prefix[r] - prefix[l]在「和约束」下移动l, r。Sliding window median窗口内中位数需双堆或对顶堆不是普通 dequeLeetCode 480。6. 常见坑与实现建议区间开闭代码里统一用[l, r)左闭右开或[l, r]闭区间与r - l、r - l 1的长度公式对应好。空窗口 / 答案初值求最短窗口时若无合法方案要明确返回0或-1不要误用INT_MAX未判断。恰好 k 与至多 k「恰好 K 个不同字符」常用exactly(k) atMost(k) - atMost(k-1)避免在窗口里硬卡「恰好」导致实现繁琐。负数与和子数组和为给定值且数组有负数 →不要假设滑动窗口和单调用前缀和 哈希见prefix_sum.md。复杂度双指针正确时每个端点最多移动O(n)次整体O(n)若内层再套一层线性查找未优化的结构可能退化成O(n²)。7. 与前缀和类技巧的区分对照场景更合适的手法定长k、和 / 均值 / 计数滑动窗口直接维护变长、正数、和 ≥ / ≤ 某值双指针滑动窗口和为k、数组含负数前缀和 哈希窗口内min / max长度 k单调队列二维矩形和多次查询二维前缀和非滑动窗口8. 一句话总结定长→ 窗口整体平移维护一个累积量或单调队列。变长→ 右扩张、左收缩用频数 / 集合判断合法性。窗口最值→单调队列下标单调 队首过期弹出。没有「扩右 / 缩左」的单调结构时不要强行滑窗改用前缀和 / 哈希等。记住「双指针」本质是每条边只朝一个方向走总移动次数线性 —— 这是滑动窗口能O(n)的根本原因。9. 推荐刷题顺序643 / 1052 / 1456定长窗口 —— 熟悉「减左加右」。3 / 209 / 340变长双指针 —— 至多约束与最短窗口。76最小覆盖子串 —— 变长 复杂合法性判断。239单调队列 —— 窗口最值模板。992 / 862进阶恰好 k、前缀和 单调队列 —— 与其它技巧综合。
滑动窗口 (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[r1]l与r同步右移。sum_new sum_old - nums[l] nums[r] 窗口整体向右滑一格C 模板区间和 / 最大平均值#includevector#includealgorithm// 长度 k 的子数组最大和若题目要平均值再除以 klonglongmaxSumFixedWindow(conststd::vectorintnums,intk){longlongsum0;for(inti0;ikistatic_castint(nums.size());i)sumnums[i];longlongbestsum;for(intrk;rstatic_castint(nums.size());r){sumnums[r]-nums[r-k];beststd::max(best,sum);}returnbest;}典型题LeetCode 643子数组最大平均数 ILeetCode 1052爱生气的书店老板定长 差量LeetCode 1456定长子串中元音的最大数目3. 变长窗口双指针「至多 / 至少」约束通用形态l、r初值均为0r从0扫到n-1先扩张r把元素纳入窗口再视条件收缩l使窗口满足题意。两类经典问法至多例如「不同元素个数 ≤ k」的最长子数组 → 不满足时收缩l。至少例如「包含所有必要字符」的最短子串 → 满足目标时再收缩l求最短。模板 A —— 长度最短正数数组子数组和 ≥targetLeetCode 209#includevector#includealgorithmintminSubArrayLen(inttarget,conststd::vectorintnums){intnstatic_castint(nums.size());longlongsum0;intl0,ansn1;for(intr0;rn;r){sumnums[r];while(sumtargetlr){ansstd::min(ans,r-l1);sum-nums[l];}}returnansn?ans:0;}模板 B —— 长度最长「至多」约束示例最多含k种不同整数的最长子数组#includevector#includeunordered_map#includealgorithmintlongestSubstringAtMostKDistinct(conststd::vectorintnums,intk){std::unordered_mapint,intcnt;intl0,ans0,distinct0;for(intr0;rstatic_castint(nums.size());r){intxnums[r];if(cnt[x]1)distinct;while(distinctklr){intynums[l];if(--cnt[y]0)--distinct;}ansstd::max(ans,r-l1);}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 992K 个不同整数的子数组恰好 k atMost(k) - atMost(k-1)正数数组 和 ≥ S 的最短子数组也可用双指针因为扩右使和增大、缩左使和减小具有单调性。若含负数则不能用纯滑动窗口求「和为 k」需换前缀和 哈希。4. 单调队列窗口长度k内的最小值 / 最大值对每个位置i求[i-k1, i]区间内的min/max单次滑动均摊O(1)维护 deque下标对应元素值单调递增求 min或单调递减求 max新元素入队前弹出队尾不满足单调性的下标若队首下标已不在窗口内则pop_front。C 模板每个窗口最大值对应 LC 239#includevector#includedequestd::vectorintmaxSlidingWindow(conststd::vectorintnums,intk){std::dequeintdq;// 存下标对应 nums 值单调递减std::vectorintans;for(inti0;istatic_castint(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(ik-1)ans.push_back(nums[dq.front()]);}returnans;}求最小值把比较改成并在输出时取nums[dq.front()]即可。典型题LeetCode 239滑动窗口最大值LeetCode 1438绝对差不超过限制的最长连续子数组定长试跑 单调队列维护 min/maxLeetCode 862和至少为 K 的最短子数组前缀和 单调队列优化进阶5. 与二分 / 前缀和的配合按列固定窗口二维矩阵里对每一行做滑动统计再组合部分「矩形」题。前缀和 窗口先算prefix[i]窗口[l, r)的和为prefix[r] - prefix[l]在「和约束」下移动l, r。Sliding window median窗口内中位数需双堆或对顶堆不是普通 dequeLeetCode 480。6. 常见坑与实现建议区间开闭代码里统一用[l, r)左闭右开或[l, r]闭区间与r - l、r - l 1的长度公式对应好。空窗口 / 答案初值求最短窗口时若无合法方案要明确返回0或-1不要误用INT_MAX未判断。恰好 k 与至多 k「恰好 K 个不同字符」常用exactly(k) atMost(k) - atMost(k-1)避免在窗口里硬卡「恰好」导致实现繁琐。负数与和子数组和为给定值且数组有负数 →不要假设滑动窗口和单调用前缀和 哈希见prefix_sum.md。复杂度双指针正确时每个端点最多移动O(n)次整体O(n)若内层再套一层线性查找未优化的结构可能退化成O(n²)。7. 与前缀和类技巧的区分对照场景更合适的手法定长k、和 / 均值 / 计数滑动窗口直接维护变长、正数、和 ≥ / ≤ 某值双指针滑动窗口和为k、数组含负数前缀和 哈希窗口内min / max长度 k单调队列二维矩形和多次查询二维前缀和非滑动窗口8. 一句话总结定长→ 窗口整体平移维护一个累积量或单调队列。变长→ 右扩张、左收缩用频数 / 集合判断合法性。窗口最值→单调队列下标单调 队首过期弹出。没有「扩右 / 缩左」的单调结构时不要强行滑窗改用前缀和 / 哈希等。记住「双指针」本质是每条边只朝一个方向走总移动次数线性 —— 这是滑动窗口能O(n)的根本原因。9. 推荐刷题顺序643 / 1052 / 1456定长窗口 —— 熟悉「减左加右」。3 / 209 / 340变长双指针 —— 至多约束与最短窗口。76最小覆盖子串 —— 变长 复杂合法性判断。239单调队列 —— 窗口最值模板。992 / 862进阶恰好 k、前缀和 单调队列 —— 与其它技巧综合。
