日野弥生：勉強しよう
LeetCode 1456 - 定长子串中元音的最大数目
发表于2025年04月21日
先求滑动窗口的最大值，然后滑动过程中不断减去开头和附加末尾，循环体循环一次求一次最大值。总体时间复杂度是O(n)。注意提前剪枝。
class Solution:
def maxVowels(self, s: str, k: int) -> int:
def isVowel(ch: str) -> bool:
return ch in "aeiou"
head, tail = 0, k
maximum = 0
currCnt = 0
for ch in range(head, tail):
if isVowel(s[ch]):
currCnt += 1
maximum = currCnt
# 提前剪枝
if maximum == k:
return k
while tail < len(s):
if isVowel(s[head]):
currCnt -= 1
if isVowel(s[tail]):
currCnt += 1
maximum = max(maximum, currCnt)
tail += 1
head += 1
# 提前剪枝
if maximum == k:
return k
return maximum