leetcode1456：定长子串中元音的最大数目（定长滑动窗口）
文章目录
- 一、 题目描述
- 二、 核心思路：定长滑动窗口
- 三、 代码实现与深度解析
- 四、 关键点与复杂度分析
- 五、 三题对比：LC1343，LC1423，LC1456
LeetCode - 1456. 定长子串中元音的最大数目，【难度：中；通过率：61.2%】，这道题要求我们在一个固定长度的“窗口”内寻找元音的最大数量，前面几道滑动窗口的入门题一样，都是最最简单的 “定长滑动窗口”，不仅如此，此题甚至不需要什么复杂的逆向思维等思维转换技巧，直接上手遍历即可
一、 题目描述
给你字符串 s 和整数 k
请返回字符串 s 中长度为 k 的任一子串中包含的元音字母的最大数目
英文中的 元音字母 为 'a', 'e', 'i', 'o', 'u'
示例:
示例 1:
输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母
示例 2:
输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母
二、 核心思路：定长滑动窗口
当问题涉及到“固定长度的连续子数组/子串”时，滑动窗口是我们的首选算法。相比于暴力遍历所有子串（时间复杂度 O(N*K)），滑动窗口可以将时间复杂度优化到 O(N)
其核心思想是：
- 维护一个大小为
k的窗口 - 当窗口向右滑动一格时，我们不需要重新计算整个窗口内的元音数量
- 我们只需要：
- 减去离开窗口的那个字符对元音数量的贡献（如果它是元音）
- 加上进入窗口的那个新字符对元音数量的贡献（如果它是元音）
- 在每次滑动后，更新我们所见过的最大元音数量
三、 代码实现与深度解析
【最简代码参考】
class Solution {public int maxVowels(String s, int k) {// 1. 初始化变量// l: 窗口的左边界（在滑动过程中更新）// cur: 当前窗口内的元音字母数量// ans: 记录所有窗口中元音字母的最大数量int l = 0, cur = 0, ans = 0;// 将字符串转换为字符数组，提高访问效率char[] arr = s.toCharArray();// 字符串的长度int len = arr.length;// 2. 计算初始窗口（第一个长度为 k 的子串）的元音字母数量int t = 0; // 临时变量，用于存储字符的值for (int i = 0; i < k; i++) {t = arr[i];// 2.1. 判断当前字符是否为元音if (t == 'a' || t == 'e' || t == 'i' || t == 'o' || t == 'u') {cur++; // 如果是元音，增加当前元音计数}}// 3. 滑动窗口遍历剩余的子串// r: 窗口的右边界，从 k 开始遍历到字符串末尾// l: 窗口的左边界，与 r 同步递增，保持窗口长度为 kfor (int r = l + k; r < len; r++, l++) {// 3.1. 处理即将离开窗口的字符（左边界字符）t = arr[l];// 3.1.1. 如果离开窗口的字符是元音if (t == 'a' || t == 'e' || t == 'i' || t == 'o' || t == 'u') {// 在字符离开窗口（cur 减小）之前，更新 ans 为当前的最大值ans = Math.max(cur, ans);cur--; // 减少当前元音计数}// 3.2. 处理即将进入窗口的字符（右边界字符）t = arr[r];// 3.2.1. 如果进入窗口的字符是元音if (t == 'a' || t == 'e' || t == 'i' || t == 'o' || t == 'u') {cur++; // 增加当前元音计数}}// 4. 返回最终结果// 4.1. 额外进行一次 Math.max 比较，以防最后一个窗口是元音数量最多的情况// （例如，所有元音都集中在字符串末尾，导致在 for 循环中没有机会更新 ans）return Math.max(cur, ans);}
}
提交结果：
四、 关键点与复杂度分析
- 定长窗口：窗口大小始终为
k，这是使用该模板的前提 - 高效更新：算法的精髓在于 O(1) 的窗口更新操作，而不是 O(k) 的重新计算
- 时间复杂度：O(N) 只需要遍历一次字符串
- 空间复杂度：O(1) 只使用了常数个额外变量来存储计数和结果
五、 三题对比：LC1343，LC1423，LC1456
这三道题都是定长滑动窗口的绝佳应用，但它们在问题的提问方式和解决策略上略有不同
| LeetCode 1343 (大小为 K 的子数组) | LeetCode 1423 (可获得的最大点数) | LeetCode 1456 (定长子串中元音的最大数目) | |
|---|---|---|---|
| 问题目标 | 统计满足条件的窗口数量 | 求两端取数后的最大和 | 求窗口内元音的最大数量 |
| 核心思想 | 定长滑动窗口 | 逆向思维 + 定长滑动窗口 | 定长滑动窗口 |
| 问题转换 | 将“平均值 >= threshold”转换为“总和 >= threshold * k”。 | 将“两端取 k 张牌最大和”转换为“中间留 n-k 张牌最小和”。 | 无，直接应用 滑动窗口 |
| 窗口内操作 | 维护窗口总和，并与 targetSum 比较 | 维护窗口总和，并不断更新 minWindowSum | 维护窗口元音计数，并不断更新 maxVowelCount |
| 算法模式 | 1. 初始化窗口。 2. 滑动。 3. 判断并计数。 | 1. 计算总和。 2. 初始化窗口。 3. 滑动。 4. 更新最小值。 5. 用总和减去最小值。 | 1. 初始化窗口。 2. 滑动。 3. 更新最大值。 |
| 时间复杂度 | O(N) | O(N) | O(N) |
| 空间复杂度 | O(1) | O(1) | O(1) |
总结与启示：
- LC1343 和 LC1456 是滑动窗口最直接的应用。它们的目标分别是“计数”和“求最值”，但核心都是遍历所有定长窗口并对窗口内的属性进行计算和判断
- LC1423 则展示了滑动窗口应用的灵活性。有时问题需要先进行一次巧妙的逆向思维转换，才能变成一个我们可以用滑动窗口解决的标准问题
通过对比这三道题，我们可以看到，虽然底层工具都是 “定长滑动窗口”，但解决问题的关键在于：
- 准确识别出“定长连续子数组/子串”这个模式
- 明确窗口需要维护的属性（是总和？还是特定元素的计数？）
- 思考是否需要对问题进行转换，才能应用该模式