LeetCode 1456中等滑动窗口
定长子串中元音的最大数目 图解题解
这道题到底在问什么
给定字符串 s 和整数 k,返回所有长度为 k 的子串里,包含元音字母最多的那个的元音数。
- 输入
- s="abciiidefou", k=3
- 输出
- 3（"iii" 三个都是元音）
最优解：一步一步想明白
- 3记住这把钥匙:定长窗口「加右一个、减左一个」O(1) 更新元音数,best 追最大。
- 4先把最左边、长度 3 的窗口建起来:第 0 个字符是 "a",是元音,绿色标出,cur 加到 1。
- 5先把最左边、长度 3 的窗口建起来:第 1 个字符是 "b",不是元音,cur 还是 1。
- 6先把最左边、长度 3 的窗口建起来:第 2 个字符是 "c",不是元音,cur 还是 1。
- 7第一个长度 3 的窗口 "abc" 建好了,里头有 1 个元音。先把它记成目前最大的 best。接下来窗口整体右滑,找元音更多的。
- 8窗口右滑一格。先把右边新进来的第 3 个字符 "i" 计入:它是元音,cur 加 1,暂时是 2。这时窗口多了一个,下一步把最左那个吐掉。
- 9再把左边移出的第 0 个字符 "a" 处理掉:它是元音,cur 减 1,新窗口 "bci" 的元音数是 1。没超过已有的 best 1,best 不动。
- 10窗口接着右移。先把右边新进来的第 4 个字符 "i" 计入:它是元音,cur 加 1,暂时是 2。这时窗口多了一个,下一步把最左那个吐掉。
- 11再把左边移出的第 1 个字符 "b" 处理掉:它不是元音,cur 不变,新窗口 "cii" 的元音数是 2。比之前的 best 还多,刷新 best = 2。
- 12再滑一格。先把右边新进来的第 5 个字符 "i" 计入:它是元音,cur 加 1,暂时是 3。这时窗口多了一个,下一步把最左那个吐掉。
- 13再把左边移出的第 2 个字符 "c" 处理掉:它不是元音,cur 不变,新窗口 "iii" 的元音数是 3。比之前的 best 还多,刷新 best = 3。
- 14窗口继续右滑。先把右边新进来的第 6 个字符 "d" 计入:它不是元音,cur 不变,暂时是 3。这时窗口多了一个,下一步把最左那个吐掉。
- 15再把左边移出的第 3 个字符 "i" 处理掉:它是元音,cur 减 1,新窗口 "iid" 的元音数是 2。没超过已有的 best 3,best 不动。
- 16窗口往右挪一格。先把右边新进来的第 7 个字符 "e" 计入:它是元音,cur 加 1,暂时是 3。这时窗口多了一个,下一步把最左那个吐掉。
- 17再把左边移出的第 4 个字符 "i" 处理掉:它是元音,cur 减 1,新窗口 "ide" 的元音数是 2。没超过已有的 best 3,best 不动。
- 18窗口再向右一步。先把右边新进来的第 8 个字符 "f" 计入:它不是元音,cur 不变,暂时是 2。这时窗口多了一个,下一步把最左那个吐掉。
- 19再把左边移出的第 5 个字符 "i" 处理掉:它是元音,cur 减 1,新窗口 "def" 的元音数是 1。没超过已有的 best 3,best 不动。
- 20窗口又滑一格。先把右边新进来的第 9 个字符 "o" 计入:它是元音,cur 加 1,暂时是 2。这时窗口多了一个,下一步把最左那个吐掉。
- 21再把左边移出的第 6 个字符 "d" 处理掉:它不是元音,cur 不变,新窗口 "efo" 的元音数是 2。没超过已有的 best 3,best 不动。
- 22最后再滑一格。先把右边新进来的第 10 个字符 "u" 计入:它是元音,cur 加 1,暂时是 3。这时窗口多了一个,下一步把最左那个吐掉。
- 23再把左边移出的第 7 个字符 "e" 处理掉:它是元音,cur 减 1,新窗口 "fou" 的元音数是 2。没超过已有的 best 3,best 不动。
- 24滑完全程,元音最多的长度 3 窗口是 "iii",3 个全是元音,这就是答案 3。回头看,我们没给任何窗口重新数过,全靠「加右一个、减左一个」一路滑下来。
⚠️ 容易写错的地方
✗ 错：每个窗口重新数元音
✓ 对：加右减左 O(1) 更新 cur
重新数是 O(n·k),滑动复用是 O(n)
✗ 错：加右时忘了同步减左
✓ 对：右滑必须「进一个、出一个」成对做
只加不减窗口就变长了,cur 不再是定长窗口的值
✗ 错：把所有字母都计入
✓ 对：只对 a/e/i/o/u 这五个加减
辅音不影响元音计数,判错就全乱
完整代码（Python / C++ / Java）
Python
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = set('aeiou')
cur = sum(ch in vowels for ch in s[:k])
best = cur
for i in range(k, len(s)):
cur += s[i] in vowels
cur -= s[i - k] in vowels
best = max(best, cur)
return bestC++
#include <algorithm>
#include <string>
using namespace std;
class Solution {
public:
int maxVowels(string s, int k) {
auto isV = [](char c){ return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'; };
int cur = 0;
for (int i = 0; i < k; ++i) cur += isV(s[i]);
int best = cur;
for (int i = k; i < (int)s.size(); ++i) {
cur += isV(s[i]);
cur -= isV(s[i-k]);
best = max(best, cur);
}
return best;
}
};Java
import java.util.*;
class Solution {
public int maxVowels(String s, int k) {
int cur = 0;
for (int i = 0; i < k; i++) cur += isV(s.charAt(i)) ? 1 : 0;
int best = cur;
for (int i = k; i < s.length(); i++) {
cur += isV(s.charAt(i)) ? 1 : 0;
cur -= isV(s.charAt(i - k)) ? 1 : 0;
best = Math.max(best, cur);
}
return best;
}
private boolean isV(char c) { return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'; }
}复杂度
时间
O(n)
建初始窗口 O(k) + 定长窗口滑一遍 O(n),整体线性
空间
O(1)
只用 cur / best 几个变量,元音集是常数大小
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 定长子串中元音的最大数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用定长滑窗而不是可变滑窗?+
因为窗口长度被题目钉死成 k,不需要左指针根据条件伸缩。这是「定长窗口」的标准模板:先建第一个窗口,再整体右移,每移一格做一次「加右减左」的 O(1) 更新。和「最长/最短满足条件子串」那类可变窗口要区分开。
如果改成统计别的字符(比如某个特定字母)出现次数,做法变吗?+
不变,只是把「是不是元音」的判断换成「是不是目标字符」,定长窗口加一减一的骨架完全一样。这类「定长窗口里某种字符计数的最值」都是同一个模板。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 定长子串中元音的最大数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。