精通定长滑动窗口：可视化指南
通过交互式可视化掌握定长滑动窗口模式。以 LeetCode 1456（最大元音数）和 LC 2653（子数组美丽值）为例，学习如何高效解决子串问题。
概述
滑动窗口（Sliding Window） 是一种基础且高效的算法技巧。它的核心思想是维护一个”窗口”区域，并在数据（如数组或字符串）上移动这个窗口，从而避免重复计算。
这是滑动窗口系列的第一篇：
- 定长窗口（本文）：窗口大小
k固定，每次向右移动一步。 - 不定长窗口：窗口大小根据条件动态伸缩（通常用于求解”最长/最短子数组”问题）。
本指南将以经典题目为例，深入讲解定长滑动窗口。
💡 核心思想
不要每次窗口移动时都重新计算整个窗口的数据。我们只需要更新变化的部分：
- 加上 新进入窗口的元素。
- 减去 刚离开窗口的元素。
通过这种优化，我们可以将 O(n·k) 的暴力算法优化为 O(n) 的线性算法。
问题一：定长子串中元音的最大数目 (LC 1456)
我们使用 LeetCode 1456: 定长子串中元音的最大数目 作为示例。
题目： 给你字符串
s和整数k。请返回字符串s中长度为k的单个子字符串中可能包含的最大元音字母数。
示例：
- 输入：
s = "abciiidef",k = 3 - 输出：
3 - 解释：子字符串
"iii"包含 3 个元音字母。
交互式可视化
让我们通过动画来看看算法是如何运行的。观察蓝色边框（窗口）是如何滑动的，以及 count 变量是如何在不重新扫描的情况下更新的。
观察： 在每一步中，我们只关注两个元素：新进入的（下标 i）和刚离开的（下标 i - k + 1）。
优化解法
暴力解法是提取所有长度为 k 的子串并计算元音，时间复杂度为 O(n·k)。当 k 很大时，这会非常慢。
滑动窗口方法允许我们在 O(n) 时间内解决这个问题。
优化技巧
- 避免使用
Set：对于只有 5 个元音字母的情况，直接判断c == 'a' || c == 'e' ...比使用Set<Character>更快且更省内存。 - 提前返回：如果我们发现某个窗口的元音数达到了
k，那么这已经是最大可能值了，可以直接返回结果。
问题二：子数组美丽值 (LC 2653)
这是一道更高级的滑动窗口问题，它将定长窗口技巧与计数排序相结合。
题目： 给你一个长度为
n的整数数组nums，找出每个长度为k的子数组的美丽值。子数组的美丽值定义为：如果子数组中存在至少
x个负数，则美丽值为第x小的负数；否则，美丽值为0。
示例：
- 输入：
nums = [1, -1, -3, -2, 3],k = 3,x = 2 - 输出：
[-1, -2, -2] - 解释：
- 子数组
[1, -1, -3]：负数排序 =[-3, -1]，第 2 小 =-1 - 子数组
[-1, -3, -2]：负数排序 =[-3, -2, -1]，第 2 小 =-2 - 子数组
[-3, -2, 3]：负数排序 =[-3, -2]，第 2 小 =-2
- 子数组
💡 关键洞察：计数排序优化
由于题目约束 -50 ≤ nums[i] ≤ 50，我们可以使用大小为 50 的计数数组来追踪负数的频率。无需对每个窗口排序，只需遍历计数数组即可在 O(50) = O(1) 时间内找到第 x 小的负数。
美丽值可视化
观察算法如何维护负数的计数数组，并在每个窗口中找到第 x 小的负数。
观察： 计数数组追踪负数（-50 到 -1）。要找到第 x 小的负数，我们从最小值（索引 0 = -50）开始扫描，累加计数直到达到 x。
子数组美丽值解法
通用模板
下面是定长滑动窗口问题的通用模板，你可以用它来解决大多数类似问题。
使用步骤：
- 初始化 状态变量（如 sum, count, hash map 等）。
- 循环 遍历数组/字符串，索引为
i。 - 添加 元素
arr[i]到状态中。 - 跳过 直到窗口大小达到
k(if (i < k - 1) continue)。 - 更新 结果（max, min 等）。
- 移除 元素
arr[i - k + 1]，为下一次迭代做准备。
复杂度分析
⏱️ 时间复杂度
O(n)，其中 n 是字符串的长度。
我们只需要遍历一次字符串。循环内部的操作（添加、移除、检查）都是 O(1) 的。
💾 空间复杂度
O(1)。
我们只使用了几个变量（count, max, i）和常数空间的辅助判断。无论输入多大，额外空间都保持不变。
下一篇
准备好挑战更复杂的滑动窗口问题了吗？继续阅读第二篇：不定长滑动窗口，你将学到：
- 如何解决”最长/最短子数组”问题
- “找最长”和”找最短”两种模式的关键区别
- 经典面试题：LC 76（最小覆盖子串）、LC 487 等