企业官网建设流程全解析

从昨天写完变长窗口的最后一题后，我就想着今天该给这个系列结个尾了。不少同学后台私信我，说滑动窗口练了几天，模板背下来了，但一换题目还是不会套，尤其是一遇到“窗口内最大值”“左边界什么时候收”就懵。这其实是绝大多数初学者的通病。今天这篇，我打算把这四天学到的滑动窗口知识彻底拉通一遍，不讲没用的概念，只讲三个东西：滑动窗口在做什么、代码模板怎么用、以及我这两天踩坑踩出来的边界经验。不管你是零基础还是刷了五十题但感觉不透彻的大一新生，看完这篇应该都能把滑动窗口这块拼图补完整。

1. 为什么说滑动窗口是“剪过枝”的暴力枚举

1.1 暴力枚举为什么能解但很亏

先说我第一天的真实状态。拿到“长度为k的子数组的最大平均值”这种题，我的第一反应就是暴力：从每个下标i开始，数k个数算平均值，再和最大值比较。逻辑完全正确，但一分析复杂度就露馅了。长度为n的数组，每个起点i都要扫描k个元素，总时间复杂度是O(n*k)。如果n是10万、k也是1万，这题基本就跑不出来了。

暴力枚举不是蠢，它是最保底的思路。关键是我们要看到它到底浪费在哪——相邻的两个窗口，其实有k-1个元素是重叠的。第一个窗口是nums[0]到nums[k-1]，第二个窗口是nums[1]到nums[k]，中间nums[1]到nums[k-1]这些元素被重复加了一遍。窗口每滑动一格，真正变化的只有两个位置：左边出去一个，右边进来一个。反复重算那k-1个没变的数，就是暴力的浪费点。

1.2 剪枝思想：砍掉重复劳动就是滑动窗口

“剪枝算法”这个词听着很高深，说白了就是一句话：把暴力过程中肯定不用算、或者刚才已经算过的东西砍掉。滑动窗口就是双指针方向上一颗非常标准的剪枝树——它不去重新计算重叠区间，而是维护一个“正在使用的窗口”，每次只处理出窗和入窗的两个元素。

还是拿最大均值举例。第一次进窗口，老老实实算sum(nums[0:k])，这个没法避免。之后每次滑动，做一次减法再加一次加法就得到新窗口的和，时间开销O(1)。这就是把O(n*k)剪枝成了O(n)。我用一个矿泉水瓶的例子记这个概念：瓶子里装了k个球，要算每k个球的总重量，你不会每次把球全倒出来重新称，只会拿走滚出去的那个、补进滚进来的那个，然后更新一下总数。滑动窗口就是这个瓶子。

1.3 什么时候该想到滑动窗口

经过四天刷题，我总结出适用滑动窗口的三个特征，遇到题直接对号入座：

• 对象是连续子数组或连续子串，不是乱序子序列；
• 问题里要求的是“满足某种条件的连续区间”，比如长度固定、和大于目标值、无重复字符；
• 区间两端能通过移动左边界和右边界来调整，而不是需要随机跳跃访问。

如果这三点同时满足，滑动窗口大概率就是出题人留给你的路子。如果题目要的是子序列而不是子数组，或者要返回所有可能的组合，那思路就应该转向动态规划或回溯，别再硬套窗口了。

2. 定长窗口：一套模板解决一大类求和/求均值题

2.1 从“第一扇窗口”开始：初始化细节定生死

定长窗口是滑动窗口里最温柔的一种，因为窗口大小k固定不动，左边界和右边界一起平移即可。先看代码再解释：

def findMaxAverage(nums, k): # 先把第一个窗口塞满 window_sum = sum(nums[:k]) max_sum = window_sum # 右边界从k开始，每次滑一格 for right in range(k, len(nums)): left = right - k window_sum = window_sum - nums[left] + nums[right] max_sum = max(max_sum, window_sum) return max_sum / k

代码很短，但有几个细节值得琢磨。第一，初始化时必须先算好第一个窗口的和，然后在循环里滑动更新，不能在循环里从零开始累积，否则第一个窗口会被重复计算。第二，left不是用另一个指针维护的，而是通过right - k算出来的，因为窗口长度固定，左边界完全由右边界决定——这是定长窗口最省心的地方。很多新手会额外写一个left变量，然后两个指针往右同步加1，结果容易在边界上出错。

2.2 一个窗口一个窗口推导：为什么整体是O(n)

我们模拟一下上面的代码跑nums = [1,12,-5,-6,50,3]，k = 4。第一个窗口是[1,12,-5,-6]，sum等于2，最大和是2。right走到4，left = 0，窗口变成[12,-5,-6,50]，sum = 2 - 1 + 50 = 51，更新最大和。right走到5，left = 1，窗口变成[-5,-6,50,3]，sum = 51 - 12 + 3 = 42，最大和保持51。

整个过程每个元素只被加进来一次、减出去一次，每个元素经历两次操作，总时间复杂度2n，也就是O(n)。对比暴力枚举的O(n*k)，数据量一大差距就是几何级的。写到这里给大家划个重点：判断你是不是真的理解了定长窗口，就看你能否立刻说出每次循环里第一个窗口和最后一个窗口是怎么处理的。

2.3 定长窗口和前缀和：工具不能乱用

刷题的时候经常能看到有人拿前缀和去解类似的题，这里我必须把两者掰扯清楚。前缀和适合回答“任意区间[l, r]的和是多少”这种静态查询问题，预处理O(n)、每次查询O(1)，但不强调窗口的移动过程；滑动窗口适合“在移动过程中维护一个动态状态”这种场景。定长窗口最大均值这种题，前者也能做，但代码会更绕一点。真正让滑动窗口无可替代的，是变长窗口——左边界的移动依赖当前窗口的状态，前缀和这种静态工具根本没法表达“状态是否满足条件”。所以判断标准很简单：如果左边界会因为条件而改变位置，就用滑动窗口；如果只是单纯随机查几个区间，前缀和更舒服。

3. 变长窗口的关键：右侧扩张，左侧收缩，何时收手

3.1 经典题：无重复字符的最长子串

定长窗口理解了之后，变长窗口才是真正考验逻辑的地方。拿我练过的最经典的变长题说事：给定一个字符串s，找出其中不含重复字符的最长子串长度。一开始我傻乎乎用暴力，把每个i作为起点往后扩，判断子串是否有重复，复杂度O(n²)。后来才意识到这就是标准的变长滑动窗口：

def lengthOfLongestSubstring(s: str) -> int: from collections import defaultdict window = defaultdict(int) # 记录窗口内每个字符出现的次数 left = 0 ans = 0 for right, ch in enumerate(s): window[ch] += 1 # 右边界进窗口 while window[ch] > 1: # 出现重复，收缩左边界直到恢复合法 window[s[left]] -= 1 left += 1 ans = max(ans, right - left + 1) return ans

核心思想总结成一句话：右指针负责扩张，左指针负责在状态不合法时收缩，窗口始终是当前右边界下最长的合法子串。右指针每走一步，我们都先把新字符放进来，然后检查窗口是否还合法。不合法就不断从左边踢字符，直到合法为止。这里的“合法”指的是窗口内没有重复字符。

3.2 左边界判断用while还是if：决定成败的一行

这个坑我印象极其深刻。上面代码第6行，如果我把while写成if，会直接挂掉。原因是：窗口里可能同时存在多个重复字符，或者一个字符重复了两次以上。比如字符串“abcb”，当right走到b时，窗口状态是“abc b”，b出现了两次，if只移除一个s[left]即a，窗口变成“bcb”，但b还是重复的，答案就错了。while则会把窗口从左边一直压缩，直到b只剩一个，最终窗口是“cb”。

初学者最容易在这犯迷糊。我后来总结了个口诀：只要收缩动作可能执行多次，就必须用while；能确定最多执行一次才用if。老老实实全用while，最多就是多循环几次，不会错。

3.3 变长窗口的通用框架

刷完“长度最小的子数组”“无重复字符的最长子串”“最小覆盖子串”这些题后，我把变长窗口总结成一个可复现的框架：

1. 初始化left = 0，创建一个用于记录窗口状态的数据结构（哈希表、计数数组、变量等）；
2. 用for循环让right从0遍历到末尾，每次把nums/right指向的元素纳入窗口状态；
3. 判断当前窗口是否不满足题目条件（比如有重复、和太大、种类太多），不满足就while收缩左边界，同步更新状态；
4. 收缩结束后，窗口是当前right下满足条件的最优窗口，用窗口长度/和/最大值去更新答案。

这个框架能覆盖大部分变长窗口题。难点在于第三步“判断不满足条件”的逻辑怎么写——这个不满足条件一定得是“随左边界收缩能恢复”的条件，而不是像“窗口所有元素之和等于target”这种并非单调的条件。一碰到后者，滑动窗口就不适用了，得考虑哈希表加前缀和。

4. 窗口最值用单调队列：把堆和暴力都比下去

4.1 先看暴力，再看堆，死因各不相同

“滑动窗口最大值”这题我卡了老半天。给定数组nums和一个滑动窗口k，要求返回每个窗口里最大的元素。我第一反应是两个方案。方案一是暴力：对每个窗口扫一遍找最大值，时间复杂度O((n-k+1)k)，也就是O(nk)，跟定长窗口暴力一样，数据一大就没了。方案二用堆：维护一个大顶堆，堆顶是最大值，每次窗口滑动就把出窗元素标记为延迟删除，入窗元素直接进堆，取答案时把堆顶已经不在窗口中的元素弹掉。这个方法能把复杂度降到O(n log k)，已经算能用了，但代码写起来琐碎——既要维护下标、又要做延迟删除，还得手动清理堆顶。

让我比较意外的是，这个题其实有更优、也更符合滑动窗口气质的解法：单调队列。它把时间复杂度压到令人舒服的O(n)。我知道有些同学第一反应是“堆都O(n log k)了，还不够快吗”，刷题平台上确实能过，但作为学算法的人，我觉得还是得搞明白O(n)的做法是怎么回事，毕竟“滑动窗口最小值/最大值”是一整套套路，掌握了模板以后遇到同类题就是默写级别。

4.2 双端队列里存下标，不存值

单调队列的思路是这样的：维护一个双端队列deque，队列里的元素按“窗口内下标递增，值单调递减”的方式存储。每次新元素入队之前，先把队尾所有“比新元素小或等于新元素”的值全部弹出，因为这些值在新元素存在期间永远不可能成为窗口最大值了——新元素更新、更大、且在窗口里存活更久。然后再把新元素下标入队。接着检查队头下标是否已经滑出窗口，滑出就弹出。最后，当窗口形成后，队头对应的值就是当前窗口最大值。

写成代码就是下面这样：

from collections import deque def maxSlidingWindow(nums, k): q = deque() # 队列里存下标，不是值 res = [] for i, v in enumerate(nums): while q and nums[q[-1]] <= v: q.pop() # 队尾那些会被v压制的下标全部踢掉 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-k+1, i]内，就说明它已经过期。如果只存值，你根本不知道它在窗口里的位置，也就没法处理过期问题。这个点是单调队列最容易栽的地方，我在第三天调试时就是因为存值结果调了半天，换成下标之后一下就通了。

4.3 单调队列为什么比堆更契合滑动窗口

打个比方，堆就像一株需要你定期修剪的老树，每次滑动都要检查树顶那颗果子是否还属于现在的窗口，不属于就得砍掉再重新看；单调队列则像一条随时自动清理的传送带，大元素进来时，把所有不可能再出头的小元素直接丢下车，剩下的永远是有资格竞争的选手。为什么能这么干？因为窗口滑动是有顺序的，元素过期也是按顺序的——新元素总是比旧元素晚过期。所以用一个队列就能同时维护“数值的优先性”和“位置的顺序性”。堆的问题在于它只维护了“数值优先”这一维度，“位置过期”只能靠额外判断补救，复杂度自然就上去了。

5. 滑动窗口里的高频翻车点和我的调试技巧

5.1 翻车点一：窗口第一次记录答案的时机

定长窗口题里，经常有人把答案更新放在滑动循环之前，或者放在窗口还没满的时候，结果少记了窗口或者记录了错误区间。我在练习时总结了两种时机，分别对应两类题：定长窗口一般是先初始化第一个窗口并记录，再从k开始滑动；变长窗口一般是窗口满足条件之后，在收缩结束、右指针固定时记录。判断时机的标准只有一个：记录答案时，窗口必须是“当前条件下的有效窗口”。既不能小于要求，也不能包含非法元素。写代码之前先在纸上把第0步、第1步模拟一遍，比写完再调试省太多时间。

5.2 翻车点二：数组下标越界的隐秘形式

变长窗口最容易碰到的越界不是left < 0或right >= n这种一眼可见的，而是状态数组访问越界。比如处理字符相关的题时用长度为26的计数数组，char - 'a'下标，如果字符串里混进了大写字母或者其他符号，瞬间就会数组越界。我吃过的亏是：用字典记录字符出现次数时，忘记检查key是否存在就做加减，Python里会报KeyError或产生错误计数。好习惯是：涉及字符统计就用长度为128的ASCII数组，或者用defaultdict，别手动判断。

5.3 我强烈推荐的手绘调试法

调试滑动窗口的题，我实验过多打日志、断点单步，效率最高的反而是最原始的方法——手写模拟表。拿“长度为k的子数组最大和”举例，我会画一张表，左边列写right，中间列写窗口区间[left, right]，右边列写执行的操作（入窗、出窗、更新答案）。每次只画5个数据点，确保循环每走一步窗口的状态都和代码输出一致。一旦发现某一步状态对不上，问题基本就锁定在那一步的代码里了。这个方法笨，但治根。我认识不少刷了上百题的老手遇到卡壳时也照样回到纸面上推演。

5.4 滑动窗口、双指针、单调栈别再搞混

刷了几天算法之后，我发现这三个东西经常被放在一起比较。严格来说，滑动窗口是双指针的一种应用，重点在于维护一个连续的区间；双指针更泛化，覆盖有序数组的相向/同向移动；单调栈则用于找“下一个更大/更小元素”这种两侧最近关系的题。我给自己的区分标准是：如果需要维护连续区间里的某种统计性质，就用滑动窗口；需要找左右两边最近的更大/更小值，用单调栈；需要比较两个序列或在有序数组里找二元组，用双指针。三者不是互相替代的关系，而是针对不同需求的不同工具。

6. 系列最后一天：留给自己和新人的刷题建议

6.1 我的分阶段题单，照着刷不迷路

这四天我给自己排了一条循序渐进的刷题路线，今天正好一并整理出来，给同样从零开始的人参考：

• 阶段一（定长窗口热身）：长度为k的子数组最大平均数、大小为K且平均值大于等于阈值的子数组数量
• 阶段二（变长窗口入门）：无重复字符的最长子串、长度最小的子数组
• 阶段三（复杂窗口统计）：最小覆盖子串、字符串的排列、找到字符串中所有字母异位词
• 阶段四（窗口最值与单调队列）：滑动窗口最大值、滑动窗口中位数、绝对差不超过限制的最长连续子数组

每个阶段我给自己定的标准是：不看题解，能独立AC两道题才算过。这个标准看着很低，执行起来就会发现比想象中难，因为看题解时觉得全懂了，关掉题解自己写时，边界条件还是会在稀奇古怪的地方出错。

6.2 最后说几句心里话

这两天总有人问我，“学长你写的模板能直接用吗”“刷完这些是不是就够了”。我的真实感受是：模板只是拐杖，理解滑动窗口的底层逻辑才是学会。如果你能自己推导出“为什么相邻窗口只有两个元素变化”“为什么左边界要用while收缩”“为什么单调队列里要存下标”，那面对任何新题，你都不会依赖背模板。对我自己来说，第四天最大的收获不是会写几道经典题，而是建立了分析框架：遇到连续子数组问题，先检查是否满足滑动窗口的适用条件，满足就按定长/变长的流程拆解，不满足就换思路。这份分析习惯，比记住任何模板都有用。滑动窗口这个系列到这里就收官了，下一篇开始，我打算继续往前进，啃一啃二分答案和单调栈这几个方向，到时候再把新的踩坑记录发出来。