题目描述
思路解析动画文字版
记住这把钥匙:定长窗口「加右一个、减左一个」O(1) 更新元音数,best 追最大。
先把最左边、长度 3 的窗口建起来:第 0 个字符是 "a",是元音,绿色标出,cur 加到 1。
先把最左边、长度 3 的窗口建起来:第 1 个字符是 "b",不是元音,cur 还是 1。
先把最左边、长度 3 的窗口建起来:第 2 个字符是 "c",不是元音,cur 还是 1。
第一个长度 3 的窗口 "abc" 建好了,里头有 1 个元音。先把它记成目前最大的 best。接下来窗口整体右滑,找元音更多的。
窗口右滑一格。先把右边新进来的第 3 个字符 "i" 计入:它是元音,cur 加 1,暂时是 2。这时窗口多了一个,下一步把最左那个吐掉。
再把左边移出的第 0 个字符 "a" 处理掉:它是元音,cur 减 1,新窗口 "bci" 的元音数是 1。没超过已有的 best 1,best 不动。
窗口接着右移。先把右边新进来的第 4 个字符 "i" 计入:它是元音,cur 加 1,暂时是 2。这时窗口多了一个,下一步把最左那个吐掉。
再把左边移出的第 1 个字符 "b" 处理掉:它不是元音,cur 不变,新窗口 "cii" 的元音数是 2。比之前的 best 还多,刷新 best = 2。
再滑一格。先把右边新进来的第 5 个字符 "i" 计入:它是元音,cur 加 1,暂时是 3。这时窗口多了一个,下一步把最左那个吐掉。
再把左边移出的第 2 个字符 "c" 处理掉:它不是元音,cur 不变,新窗口 "iii" 的元音数是 3。比之前的 best 还多,刷新 best = 3。
窗口继续右滑。先把右边新进来的第 6 个字符 "d" 计入:它不是元音,cur 不变,暂时是 3。这时窗口多了一个,下一步把最左那个吐掉。
再把左边移出的第 3 个字符 "i" 处理掉:它是元音,cur 减 1,新窗口 "iid" 的元音数是 2。没超过已有的 best 3,best 不动。
窗口往右挪一格。先把右边新进来的第 7 个字符 "e" 计入:它是元音,cur 加 1,暂时是 3。这时窗口多了一个,下一步把最左那个吐掉。
再把左边移出的第 4 个字符 "i" 处理掉:它是元音,cur 减 1,新窗口 "ide" 的元音数是 2。没超过已有的 best 3,best 不动。
窗口再向右一步。先把右边新进来的第 8 个字符 "f" 计入:它不是元音,cur 不变,暂时是 2。这时窗口多了一个,下一步把最左那个吐掉。
再把左边移出的第 5 个字符 "i" 处理掉:它是元音,cur 减 1,新窗口 "def" 的元音数是 1。没超过已有的 best 3,best 不动。
窗口又滑一格。先把右边新进来的第 9 个字符 "o" 计入:它是元音,cur 加 1,暂时是 2。这时窗口多了一个,下一步把最左那个吐掉。
再把左边移出的第 6 个字符 "d" 处理掉:它不是元音,cur 不变,新窗口 "efo" 的元音数是 2。没超过已有的 best 3,best 不动。
最后再滑一格。先把右边新进来的第 10 个字符 "u" 计入:它是元音,cur 加 1,暂时是 3。这时窗口多了一个,下一步把最左那个吐掉。
再把左边移出的第 7 个字符 "e" 处理掉:它是元音,cur 减 1,新窗口 "fou" 的元音数是 2。没超过已有的 best 3,best 不动。
滑完全程,元音最多的长度 3 窗口是 "iii",3 个全是元音,这就是答案 3。回头看,我们没给任何窗口重新数过,全靠「加右一个、减左一个」一路滑下来。
边界先想清:k=n 数整串、全元音得 k、无元音得 0、k=1 看单字符。
面试常考:认出「定长窗口」模板,以及它和可变窗口的区别。
参考代码
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 best复杂度
- 时间：O(n)，建初始窗口 O(k) + 定长窗口滑一遍 O(n),整体线性
- 空间：O(1)，只用 cur / best 几个变量,元音集是常数大小
易错点
面试追问把动画讲成自己的话
追问这道题为什么用定长滑窗而不是可变滑窗?
追问如果改成统计别的字符(比如某个特定字母)出现次数,做法变吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删掉一个元素以后全为 1 的最长子数组
LeetCode 1493 · 中等 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题