定长滑动窗口
定长滑动窗口的 in/out/update-ans 三段式模板与边界处理
1. 核心原理
定长滑动窗口要解决的问题模板长这样："给你一个数组（或字符串），求所有长度为 k 的连续子区间中，某个统计量（和 / 元音数 / 不同元素数 / 平均值）的最大 / 最小 / 计数"。
暴力解为什么是 O(nk)？
最朴素的写法是双层循环：外层枚举每个窗口的起点 i（共 $n-k+1$ 个），内层从 i 扫到 i+k-1 重新算一遍统计量。每个窗口算一次要 $O(k)$，总共就是 $O((n-k+1) \cdot k) \approx O(nk)$。当 $n = 10^5, k = 10^3$ 时，这是 $10^8$ 次操作，在 1s 时限的 OJ 上会 TLE。
滑动窗口为什么能压到 O(n)？
关键洞察：右端往右滑一格时，窗口只进一出一，旧窗口的统计量可以直接复用。
旧窗口: [a b c] d e 统计量 S_old = f(a,b,c)
新窗口: a [b c d] e 统计量 S_new = S_old - a + d每次更新只花 $O(1)$，总共 $n - k + 1$ 次更新，外加初始化第一个窗口的 $O(k)$，整体复杂度 $O(n)$。同样的 $n=10^5, k=10^3$ 输入，运算量从 $10^8$ 降到 $10^5$，缩减约 1000 倍。
模板三段式
定长滑窗常用作电话轮的开场题，时间预算约 5 分钟，可以在剩下时间追问 follow-up（如改成不定长、改成流式、改成多线程）。模板固定为三步：
- in：把新进入窗口的元素纳入统计
- out：把离开窗口的元素从统计中剔除（仅当窗口已满）
- update-ans：当窗口恰好为长度 k 时，更新答案
三步顺序固定：先 in，窗口满后 out，最后 update-ans。
2. 图解
以数组 [2, 1, 5, 1, 3, 2]、k = 3 为例，求最大窗口和。下面 4 个快照演示窗口如何"滚"过整个数组（+ 表示 in，- 表示 out）：
Step 1: [ 2 1 5 ] 1 3 2 sum = 2+1+5 = 8 (in: +2,+1,+5)
l r ans = 8
Step 2: 2 [ 1 5 1 ] 3 2 sum = 8 - 2 + 1 = 7 (in: +1, out: -2)
l r ans = max(8, 7) = 8
Step 3: 2 1 [ 5 1 3 ] 2 sum = 7 - 1 + 3 = 9 (in: +3, out: -1)
l r ans = max(8, 9) = 9
Step 4: 2 1 5 [ 1 3 2 ] sum = 9 - 5 + 2 = 6 (in: +2, out: -5)
l r ans = max(9, 6) = 9注意三个细节：
- Step 1 是"初始化阶段"，需要把前 k 个元素一次性塞进窗口才能开始滚动
- 从 Step 2 起，每一步只触发 1 次 in + 1 次 out + 1 次 update-ans，恒定 $O(1)$
- 最终答案
ans = 9，出现在 Step 3 的窗口[5, 1, 3]
定长滑动窗口
窗口大小 k = 3，左端 l 与右端 r 同步右移
3. 母题精讲
LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length
题目（中文翻译）：给定字符串 s 和整数 k，返回 s 中长度为 k 的子串里所含元音字母数量的最大值。元音包括 'a', 'e', 'i', 'o', 'u'（仅小写）。
样例 1：
输入: s = "abciiidef", k = 3
输出: 3
解释: 子串 "iii" 包含 3 个元音，达到最大。样例 2：
输入: s = "leetcode", k = 3
输出: 2
解释: 子串 "lee" / "eet" / "ode" 都含 2 个元音。思路推导
把"窗口的统计量"具体化为"窗口内的元音个数"。
- in：右端新进的字符若是元音，
cnt += 1 - out：左端被挤出的字符若是元音，
cnt -= 1 - update-ans：每当窗口长度恰为 k 时，
ans = max(ans, cnt)
为了把"是否元音"的判定压到 $O(1)$，用 frozenset 预存元音集合 —— Python 的 set 平均查找是 $O(1)$，frozenset 不可变更安全。
工业级实现（多语言对照）
class Solution:
def maxVowels(self, s: str, k: int) -> int:
# 预处理元音集合: frozenset 提供 O(1) 查找, 且不可变, 多线程安全
VOWELS = frozenset("aeiou")
n = len(s)
# 边界: 若 k 超过串长, 题目保证 1 <= k <= n, 这里保险起见返回 0
if k > n or k <= 0:
return 0
cnt = 0 # 当前窗口内的元音个数
ans = 0 # 全局最大元音个数
for i, ch in enumerate(s):
# ---------- 1) in: 右端纳入新字符 ----------
if ch in VOWELS:
cnt += 1
# ---------- 2) out: 窗口超长时弹出左端 ----------
if i >= k and s[i - k] in VOWELS:
cnt -= 1
# ---------- 3) update-ans: 窗口恰好为 k 时更新答案 ----------
if i >= k - 1:
if cnt > ans:
ans = cnt
# 小优化: 已达理论上限 k 直接提前返回
if ans == k:
return ans
return ansclass Solution {
public int maxVowels(String s, int k) {
int n = s.length();
int cnt = 0, ans = 0;
for (int i = 0; i < n; i++) {
// 1) in
if (isVowel(s.charAt(i))) cnt++;
// 2) out
if (i >= k && isVowel(s.charAt(i - k))) cnt--;
// 3) update-ans
if (i >= k - 1) {
ans = Math.max(ans, cnt);
if (ans == k) return ans; // 提前剪枝
}
}
return ans;
}
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}class Solution {
public:
int maxVowels(string s, int k) {
auto isVowel = [](char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
};
int n = s.size();
int cnt = 0, ans = 0;
for (int i = 0; i < n; ++i) {
// 1) in
if (isVowel(s[i])) ++cnt;
// 2) out
if (i >= k && isVowel(s[i - k])) --cnt;
// 3) update-ans
if (i >= k - 1) {
ans = max(ans, cnt);
if (ans == k) return ans;
}
}
return ans;
}
};代码逐段讲解
变量含义：
VOWELS：元音字符集，frozenset是不可变set，查找 $O(1)$ 且声明在 class 里时是安全的全局常量cnt：滚动维护的"当前窗口元音个数"，是这道题的核心统计量ans：从初始 0 开始，单调不减地记录历史最大值
初始化为什么是 0？ 因为窗口尚未形成时窗口内没有元素，元音数自然是 0。ans = 0 是合法下界，元音数永远 $\geq 0$。
循环不变量：当循环执行完第 i 次迭代后，cnt 始终等于子串 s[max(0, i-k+1) .. i] 中的元音个数。在 i >= k - 1 时，这个子串长度恰为 k，可以拿去更新答案。
边界i >= k - 1 为什么这样写？ Python 下标从 0 起，当 i = k - 1 时窗口覆盖 s[0..k-1] 共 k 个字符，是第一次满窗。再往前的 i 都属于"初始化阶段"，不能更新答案。
i >= k 为什么不是 i > k？ 当 i = k 时，窗口左边界是 i - k = 0，要把 s[0] 弹出。如果写成 i > k，会漏掉这次弹出，导致 cnt 多算一个。
4. 边界条件拆解
(1) k > n 时怎么办：题目通常保证 1 <= k <= n，但工业代码最好显式判一下。若 k > n，第一个完整窗口都凑不齐，直接返回 0（或按业务定义返回特殊值，如 -1）。在我们的实现里，循环里 i >= k - 1 永远不成立，ans 保持初值 0，行为正确，但提前 return 可以省掉无意义的 n 次循环。
(2) k == 0 或空串：k == 0 意味着空窗口，统计量没有意义；空串 s = "" 时 n = 0，无窗口可滑。两种情况都应在入口处直接返回 0，否则 i >= k - 1 在 k == 0 时退化为 i >= -1 恒真，会错误地在空窗口上更新答案。
(3) 滚动状态初始化（先攒满 vs. 用 i < k 兜底）：两种主流写法。写法 A：先用一个独立循环 for i in range(k) 把第一个窗口算出来，再从 i = k 开始滚动；写法 B（本文采用）：单循环 + i >= k 控制 out、i >= k - 1 控制 update-ans。写法 A 思路清晰但代码长；写法 B 紧凑且只扫一遍，但条件判断容易写错。面试推荐写法 B，代码量少更显熟练。
(4) Unicode / 大写元音的陷阱：本题明确说"仅小写元音"，但实际面试中面试官可能追问"如果包含大写 A、E、I、O、U 呢"或者"如果是 Unicode 字符串呢"。解决方案：把判定换成 ch.lower() in VOWELS，但要警惕 str.lower() 在某些 Unicode 字符（如土耳其语 'İ'）下会改变字符串长度，导致下标失配。严谨做法：先对整个 s 做一次 s = s.casefold() 预处理，确保后续判断是字符级别一一对应。
5. 复杂度分析
- 时间复杂度：$O(n)$ — 每个字符进入窗口一次、离开窗口一次，加上 $O(1)$ 的判定与计数
- 空间复杂度：$O(1)$ —
VOWELS是常量大小（5 个字符）的集合，其它都是标量变量 - 暴力 $O(nk)$ vs. 滑窗 $O(n)$ 的真实差距：以 $n = 10^5, k = 10^3$ 为例
- 暴力：$10^5 \times 10^3 = 10^8$ 次操作，约 1 秒，LeetCode 卡线 TLE
- 滑窗：$10^5$ 次操作，约 1 毫秒
在高频更新场景下，O(n) 与 O(nk) 的差距决定能否在线处理流式数据。
6. 通用模板
通用骨架如下，按题目把 contribute / update / INIT 填进去：
# 定长滑动窗口三段式模板 (窗口大小 = k)
cnt, ans = 0, INIT # 初始化窗口统计量与答案
for i, x in enumerate(arr):
cnt += contribute(x) # 1) in: 新元素纳入
if i >= k:
cnt -= contribute(arr[i-k]) # 2) out: 旧元素弹出
if i >= k - 1:
ans = update(ans, cnt) # 3) update-ans: 窗口满则更新答案
return ans其中：
contribute(x)：把元素x转化为对统计量的贡献（如本题就是1 if x in VOWELS else 0）update(ans, cnt)：根据题意取 max / min / 累加 / 计数等INIT：根据题意定 0 /-inf/+inf
与其他模式的边界
定长滑窗只是这一族技术的入口。下面几条边界说清楚什么时候要切到别的工具：
| 题目特征 | 用什么 | 原因 |
|---|---|---|
| 窗口长度由条件触发（满足/不满足某性质） | 不定长滑窗 | 收缩条件由窗口内部状态决定，不是固定 k |
| 求窗口内的最大/最小值（不是和、不是计数） | 单调队列（monotonic deque） | 维护"还可能成为答案"的候选；定长滑窗也能套，但需要 O(log k) 用堆 |
| 区间和的离线查询（多次询问、窗口起点任意） | 前缀和 | 任意区间和 O(1) 直接查；滑窗只适合"按顺序枚举所有窗口"的场景 |
| 元素不连续（需要从数组中跳着选） | 滑窗不适用 | 滑窗的核心前提是"窗口在原数组上连续平移"，跳着选意味着子集而非子段 |
| 需要排序后才能定位窗口 | 排序 + 双指针 / 二分 | 排序破坏原顺序，滑窗失去意义 |
举一个反例：LC 217 数组中是否存在重复元素，看起来像"滑窗求 distinct"，但没有窗口长度约束——其实是 set 一遍扫的题，滑窗杀鸡用牛刀。再举一个：LC 1248 优美子数组个数，需要数子数组总数而不是某窗口的属性，需用滑窗变体（不定长 + 计数差），不是定长。