企业官网建设流程全解析

做算法题的人应该都经历过这种尴尬：暴力枚举的思路写得飞快，一提交就超时。我第一次看到"滑动窗口"这个词，以为是一种很高级的专门数据结构，后来才搞明白它其实没什么花哨，就是把暴力枚举里的重复计算省掉，把时间复杂度从 O(n^2) 压到 O(n)。这篇文章写的是我这些年实际刷题、面试和做工程里反复用到滑动窗口的经验总结。无论你是在准备算法工程师面试，还是刚入门数据结构与算法，又或者只是想刷完 LeetCode 上那批必刷基础算法题，滑动窗口都值得你花一个下午认真吃透。

1. 滑动窗口解决的是哪一类问题

1.1 为什么暴力枚举会超时

先拿最经典的"长度最小的子数组"举例。题目问：给定一个正整数数组 nums 和一个目标值 target，找到和大于等于 target 的连续子数组的最小长度，没有就返回 0。

新手的第一反应基本都是两层循环，枚举每个起点，再往右不断累加，直到 sum >= target 就更新答案。逻辑没有错，但一遇到 n=10^5 的测试用例就超时。原因很简单：对于每个起点，都要重新从起点扫到终点，很多区间被重复遍历。比如起点 0 算到下标 100，起点 1 又从下标 1 算到 100，中间下标 2 到 100 这一段被反复加了一遍又一遍。

暴力枚举耗时的地方不是"枚举起点"这个动作，而是重复计算。滑动窗口恰恰是冲着这个重复计算来的。

1.2 窗口滑动到底省掉了什么计算

滑动窗口的核心思想是维护一个连续区间，让区间左边界 left 和右边界 right 在数组上移动。右边界负责把新元素加入当前区间，左边界负责把不满足条件的旧元素移出去。

拿 [2, 3, 1, 2, 4, 3]，target = 7 这段数据走一遍。right 从 0 开始往右加，依次得到 2、5、6、8。加到下标 3 时，和已经等于 8，满足 >= 7，于是记录长度 4。这时候从下标 1 开始的子数组不必重新枚举，只需要把 left 从 0 移到 1，sum 减掉 nums[0] 变成 6，然后 right 继续往前加。

这就是关键：每移动一次窗口，只需要处理头尾两个元素的变化，中间那段已经被上一轮的结果复用了。整体上每个元素进窗口一次、出窗口一次，均摊时间复杂度 O(n)。

生活里也有类似的体验：你统计一辆公交车连续 30 天的总客流，如果每天都从第一天重新加一遍，那是暴力的；更好的做法是维护一个"最近 30 天"的总数，新的一天加进来，第三十一天对应的那一天减掉。滑动窗口就是这个记账本。

1.3 适用场景与不适合的场景

滑动窗口不是万能的。我刚开始学的时候，看到什么题都往窗口上套，结果经常翻车。后来总结出它能用的前提条件：

如果题目要你找的是"子序列"，不是连续区间，滑动窗口就不适用。如果数组里有负数，"窗口越大和越大"这个单调性就没了，滑动窗口也不能直接套，通常要转前缀和加哈希表。

一句话：滑动窗口是优化连续区间暴力枚举的框架，不是包治百病的算法。

2. 定长窗口与变长窗口：先分清两条路线

2.1 定长窗口：滑动一个固定大小框

定长窗口最好理解，窗口长度始终是 k。右边界每步向右移动一格，左边界也跟着向右移动一格，一进一出，窗口大小不变。适合解决"大小为 k 的连续子数组的最大平均值""固定窗口中的最大值"这类问题。

定长窗口的实现套路是：先初始化前 k 个元素，然后从下标 k 开始循环，每次加入 nums[right]，移除 nums[right - k]，再更新答案。注意这里移除的是刚好滑出窗口的那个元素，下标对应关系最容易写错，后面排查章节我会专门说。

只走一遍，所以时间复杂度 O(n)。定长窗口在工程里也很有用，比如监控系统里统计最近 10 分钟的错误日志数，就是一个定长时间窗的滑动计数。

2.2 变长窗口：右指针扩张、左指针收缩

变长窗口比定长窗口更常考。它的双指针规则很朴素：

• right 向右扩张，扩大窗口；
• 一旦窗口不再满足条件，left 向右收缩，直到窗口重新满足条件；
• 在窗口满足条件期间更新答案。

还是用长度最小的子数组来说。right 不断加元素，只要 sum >= target，就尝试把 left 往右缩，因为我要找的是"最小长度"，能缩就缩，记录更短的答案。等 sum < target 了，再让 right 继续走。

这个"缩到刚好满足，甚至直到刚好不满足"的过程，正是滑动窗口最容易出错的地方。很多人喜欢用 if 而不是 while，缩一次就停，最后统计的答案偏大，因为窗口里还留着不该留的冗余元素。

变长窗口的时间复杂度同样是 O(n)。两个指针可能会让新手觉得像是"来回扫了很多遍"，实际上 left 和 right 各自只向右移动，每个元素最多被添加一次、删除一次。

2.3 窗口状态的三件套：哈希表、频次数组与累计和

窗口里需要维护什么，决定了你选哪种"状态容器"。

• 累计和：像上面 target 这种题，只需要一个变量 total，进入窗口加值，离开窗口减值。
• 频次数组：题目要求统计字符出现的次数，比如"无重复字符的最长子串"里，可以用一个长度为 128 或 256 的数组记录字符频次，比哈希表更快。
• 哈希表：当字符集很大或需要记录位置时，哈希表更灵活，比如记录字符最后一次出现的下标。
• 双端队列：涉及窗口最值问题，比如"滑动窗口最大值"，队列不仅存值，还要存索引，后面专门讲。

选择标准只有一个：更新一次窗口时，状态的维护能不能做到 O(1)。如果做不到，滑动窗口的均摊 O(n) 就被破坏了。

3. 四道经典题手撕：从基础题到压轴题

3.1 长度最小的子数组：最标准的变长窗口

这是滑动窗口的入门题，LeetCode 第 209 题。前面我已经讲了思路，直接上代码，基于常见实践写得比较精简：

def min_sub_array_len(target: int, nums: List[int]) -> int: left = 0 total = 0 ans = len(nums) + 1 for right, value in enumerate(nums): total += value while total >= target: ans = min(ans, right - left + 1) total -= nums[left] left += 1 return 0 if ans == len(nums) + 1 else ans

有几个细节值得注意。第一，ans 初始值设成一个不可能的大值，比如 len(nums) + 1，最后判断是否更新过。第二，while 内部先记录答案再缩小窗口，顺序反了会漏掉最优解。第三，当 total 减掉 nums[left] 后可能仍然 >= target，所以要继续 while，不能只 if 一次。

如果所有元素相加都不到 target，ans 不会被更新，返回 0 即可。

3.2 无重复字符的最长子串：哈希表变长窗口

这题是面试高频中的高频，LeetCode 第 3 题。两种常见写法，我建议都掌握。

第一种是哈希表记录字符最后出现的下标，通过一次跳跃完成去重：

def length_of_longest_substring(s: str) -> int: left = 0 ans = 0 last_index = {} for right, ch in enumerate(s): if ch in last_index and last_index[ch] >= left: left = last_index[ch] + 1 last_index[ch] = right ans = max(ans, right - left + 1) return ans

这里 last_index[ch] >= left 的判断必不可少。如果不加，哈希表里存的可能是上一次窗口之外已经删掉的位置，left 会被错误地回退。

第二种是用 set 维护当前窗口内字符集合，配合 while 删除重复字符：

def length_of_longest_substring(s: str) -> int: window = set() left = 0 ans = 0 for right, ch in enumerate(s): while ch in window: window.remove(s[left]) left += 1 window.add(ch) ans = max(ans, right - left + 1) return ans

这种写法更贴近"窗口"的原始语义，也更容易理解 left 收缩的过程。哈希表写法虽然少几次删除操作，但边界判断多，面试时容易说漏条件。我个人建议新手先用 set 版本把逻辑理顺，再去看哈希表版本的优化。

3.3 滑动窗口最大值：单调队列救场

LeetCode 第 239 题，这题暴力解法很容易想到：每个窗口内扫一遍找最大值，复杂度 O(nk)。当 k 接近 n 时就是个 O(n^2)，基本不可用。

正确的解法是维护一个单调递减队列。队列从队首到队尾，值严格递减，队首永远是当前窗口的最大值。核心代码如下：

from collections import deque def max_sliding_window(nums: List[int], k: int) -> List[int]: q = deque() ans = [] for i, x in enumerate(nums): # 移除已经滑出窗口的过期下标 if q and q[0] <= i - k: q.popleft() # 保持队列单调递减，队尾比当前值小的元素直接淘汰 while q and nums[q[-1]] <= x: q.pop() q.append(i) # 窗口成型后再记录最大值 if i >= k - 1: ans.append(nums[q[0]]) return ans

不要小看这个 while 弹出的操作。它淘汰的是"永远不可能成为最大值"的旧元素：更靠左、值又比当前元素小，当前元素会在窗口里留更久，所以旧元素直接被丢。每个元素最多入队一次、出队一次，均摊 O(n)。

3.4 最小覆盖子串：两个指针加频次表

这题是变长滑动窗口的进阶题，LeetCode 第 76 题，面试里属于硬骨头。要求从字符串 s 里找出包含字符串 t 全部字符的最短子串，t 里的字符可以重复。

思路是用两个指针滑动，同时维护 t 中每个字符还缺多少个。missing 变量表示还缺多少个字符，等于 0 时说明窗口已经覆盖完所有必需字符。此时尝试收缩 left，去掉左侧多余字符，记录更短结果后，再主动破坏窗口条件，继续向右寻找新的候选。

def min_window(s: str, t: str) -> str: need = {} for c in t: need[c] = need.get(c, 0) + 1 missing = len(t) left = 0 start = 0 min_len = float('inf') for right, c in enumerate(s): if need.get(c, 0) > 0: missing -= 1 need[c] = need.get(c, 0) - 1 if missing == 0: # 收缩左侧多余字符 while need[s[left]] < 0: need[s[left]] += 1 left += 1 if right - left + 1 < min_len: min_len = right - left + 1 start = left # 主动移除一个必需字符，让窗口重新进入“不完整”状态 need[s[left]] += 1 missing += 1 left += 1 return "" if min_len == float('inf') else s[start:start + min_len]

这段代码最反直觉的地方在最后三步。窗口已经满足条件且记录完答案后，我们要故意从左边拿走一个必需的字符，让 missing 重新大于 0，否则 right 继续往前加，窗口只会越来越大，永远收缩不了。很多人在这个位置卡住，想不通为什么满足条件了还要破坏它。

这正是滑动窗口的精髓：窗口满足条件时要及时尝试压缩，压缩到头后，就主动退出条件，让右指针继续寻找下一段可行的起点。

4. 单调队列：滑动窗口的隐藏王牌

4.1 为什么窗口最值要单独开一节

前面讲过的哈希表、频次数组能维护窗口内"有哪些元素""各有几个"，但维护不了"最大值是谁"。窗口滑动时，最大值可能被移除，剩下谁是最大，需要重新比较；哈希表完全帮不上忙。

有人会说用堆。但是堆只能拿到全局最大，而且删除任意元素不是 O(logn) 的直接操作。标准库的优先队列只能删堆顶，无法方便地删掉"滑出窗口的那个元素"。如果改用懒删除堆，又得配合延迟删除，代码复杂度直线上升。

单调队列解决的正是这类场景。它本质上是一个双端队列，同时做到三件事：队首能取当前窗口最大；能快速移除过期元素；能把自己变成单调有序。很多资料把单调队列和单调栈放在一起讲，但两者结构差异很大：单调栈只在一端进出，单调队列两端都能操作，因为窗口的过期删除发生在左侧。

4.2 单调队列三种操作的正确顺序

具体写单调队列时，操作顺序必须固定，我见过不少把顺序写反导致答案错误的。顺序是：

1. 清过期：队首元素如果下标已经小于等于 i - k，说明它已经不在当前窗口里，popleft 移除。
2. 清逆序：队尾元素如果小于等于当前值，说明它在当前窗口内永远不可能成为最大值，pop 掉。
3. 入队并取结果：当前下标入队，窗口完整时取队首元素。

为什么先清过期再清逆序？如果先做单调弹出，一个已经不在窗口里的旧值可能还占着队首，导致后面的弹出比较使用了错误基线。反过来，如果先清过期，队首一定是当前窗口里的元素，后续单调维护才准确。

4.3 单调队列的边界条件与容易踩的坑

队列里到底存值还是存下标，是一个很关键的选择。我强烈建议存下标，因为值同样大时，只有下标能判断是否过期。比如 nums = [5, 3, 7]，窗口大小 2，队里存下标才能正确判断下一个最大值是否还在窗口内。

弹出时用<还是<=也有讲究。用<=会更激进，把值相等的旧元素也弹掉，保留较新的下标。对求"最大值"这种题，结果不受影响，但新元素下标更大，更晚过期，代码更稳。需要求"最小值"时，只要把单调递减改成单调递增，也就是把比较方向反过来即可。

另一个常见坑是收集答案的位置。必须是i >= k - 1之后再取队首，因为窗口还没形成完整 k 个元素时，队首只能代表当前局部状况，不是最终答案。答在i < k - 1时取结果，由于窗口长度不足，结果必然是错的。

5. 常见的翻车现场与排查技巧

5.1 症状表：死循环、漏解、错解

我自己的经验里，滑动窗口出错一般不是思路问题，而是代码细节问题。下面这张表是典型的"症状-原因-修复"对照：

排查这类问题，最快的办法不是看代码，而是把 few 个极短的用例手工跑一遍。比如 nums = [1, 1, 1]、target = 2，输出应该是 2；跑完能发现 left 收缩时机的问题。

5.2 为什么收缩必须用 while，不能只 if 一次

很多数据库类比里，"if 收缩一次"可能就够了，但滑动窗口不行。比如这个场景：当前窗口和已经远远大于 target，left 每移动一步，窗口和仍然大于 target。如果只移动一次就记录答案，那么你不是在找"最小长度"，而是在记录"第一个满足条件的长度"，大概率会错过更短窗口。

再比如最小覆盖子串里，left 左边可能有连续一堆多余字符，比如 s 是 AABBXC，左边界在 A 处，可能右侧还堆着另一个 A。只移动一次，窗口里依然有多余字符，记录的就不是最紧凑的覆盖子串。

所以在滑动窗口里，"满足条件"和"可以继续压缩"是两个不同的判定，它们都需要用 while 来完成。如果发现某段代码只能用 if 才能通过，通常意味着你误用了滑动窗口的单调性假设。

5.3 现场自检：三个必测用例

我在面试和笔试里总结出三个高频自测用例，基本一测一个准：

• 空输入：nums 为空、s 为空、k 为 0。很多代码在空数组上会直接返回错误结果，或者栈溢出，一开始就要处理。
• 窗口大小等于整个数组：k = n，定长窗口只会产生一个结果，检验单调队列是否在窗口成型后正确取队首。
• 所有元素相同：比如 [1,1,1,1,1]，配合 target 或 k，最容易暴露过期判断和弹出方向的问题。

还有一类更隐蔽的用例是 target 等于数组里单个元素的最大值。长度最小的子数组，当 target 恰好等于某个数时，答案应为 1，很多实现因为 while 条件写反会输出 2。测试时把目标值设成单点值，立刻看出问题。

6. 从面试题到工程实践

6.1 不同语言的实现差异

Python 里用列表模拟队列不是不行，但 popleft 操作如果是pop(0)，代价是 O(n)，直接用collections.deque最稳妥。Java 里可以用ArrayDeque，注意它不允许 null 元素，存索引时没这个问题。C++ 可以用std::deque存下标，逻辑完全一样。

如果只需要维护累计和，没有任何语言差异，一个 int 就能解决。一旦涉及窗口内最值，优先用双端队列容器，不要用手写数组模拟，减少边界劳动。

实测下来的经验是：Python 写滑动窗口最舒服，但面试时如果要求你分析队列里为什么每个元素最多进出一次，建议手画一遍三个操作的小例子，比干背结论更有说服力。

6.2 滑动窗口在监控、限流和流式统计里怎么用

滑动窗口不只是面试题，工程里几乎是标配。

日志监控里统计最近 5 分钟的错误率，就是一个时间维度的滑动窗口。数据源源不断进来，新的错误计数加进去，5 分钟之前的数据从另一头移除，不需要每次从全量日志里重算。流式计算框架里的 tumbling window 和 sliding window，本质就是定长窗口的工程化实现。

限流场景里，固定窗口策略在窗口边界可能出现两倍流量突刺，滑动窗口限流把时间切成更小的桶，每次请求动态检查整段窗口内的用量，平滑很多。我自己做网关限流时，就是用类似滑动窗口的计数方式；虽然细节比算法题的数组复杂，但核心思想完全一样：维护一段连续区间，头部新增，尾部淘汰，中间状态复用。

还有一件事值得澄清：网络协议里的"滑动窗口重传协议"，和算法里的滑动窗口不是同一个概念，前者是流量控制和可靠传输机制，不要面试时把它们混在一起讲。它们的共同点只是都用了"窗口长度可动态调整"这个抽象。

6.3 延伸：滑动窗口与单调栈、前缀和的配合

滑动窗口不是孤立算法，它经常要和别的手段配合。

数组里如果有负数，"窗口越大数值单调性越强"就不再成立，这时不能直接滑。常见的改造方式是前缀和加哈希表，或者把问题转化成"满足区间和的个数"这类询问。碰到这类题，先判断单调性，再决定上不上滑动窗口。

滑动窗口和单调栈的组合也很有意思。比如计算直方图最大矩形面积时，用单调栈找左右边界；而滑动窗口求最大时，用单调队列找区间最值。两者都是"把不可能成为答案的候选尽快淘汰"，但一个维护栈结构，一个维护队列结构。

如果你刷题时感觉某道题可以用滑动窗口但又找不到收缩条件，可以想想：它是不是需要先排序？或者需要前缀和？这些都是常见的延伸方向。把这些组合关系理清楚，刷 LeetCode 必刷基础算法题时，你就不会再看到一个"连续子数组"就无脑套窗口了。

写到这里，我想起自己面试时最容易紧张的点就是滑动窗口的边界条件。后来我养成一个习惯：写完代码先不急着提交，手动构造一个最小用例，把 left 和 right 的每一步变化写在纸上。只要这个过程能顺畅走通，代码基本不会差太远。滑动窗口本身不难，它难的是把一个看似朴素的双指针想法，写成没有边界漏洞的代码。这份手感，真的只能靠多跑几遍题来积累。