LeetCode 1456. 定长子串中元音的最大数目

2021-08-05 HGNULB 约 9 分钟

文章信息 7 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 1-2 字节跳动 LeetCode 75

题目描述

✅ 1456. 定长子串中元音的最大数目

题意分析

给一个小写字母串 s 和整数 k，在所有长度恰好为 k 的连续子串中，找出元音字母（a、e、i、o、u）最多的那一个，返回它的元音个数。

两个词决定了整道题的形态。「连续」意味着候选区间只有 n - k + 1 个，而不是组合数级别；「长度恰好为 k」意味着区间长度是固定的，不需要根据某个条件去伸缩左边界——这和「最长/最短满足某条件的子串」那一类题有本质区别，本题的两个端点是绑定同步移动的。

约束里 1 <= k <= s.length <= 10^5。k 不超过串长这一点很重要：它保证了至少存在一个合法窗口，初始化时可以放心地先填满前 k 个字符，不必担心越界或「无解」。串长 $10^5$ 也把 $O(nk)$ 的暴力挡在了门外（最坏 $10^{10}$ 次比较）。

元音只有 5 个固定字符，判定是纯粹的 $O(1)$ 常数操作，不需要哈希集合，一个五路 || 或一个长度 26 的布尔表就够。

边界有三类：k == s.length() 时只有一个窗口，答案就是全串元音数；k == 1 时答案是 0 或 1，取决于串里有没有元音；全是辅音时答案为 0，此时不能因为「没找到」而返回 -1 之类的哨兵。另外一个隐蔽的上界是：答案最大就是 k，若中途已经达到 k 其实可以提前返回，但没必要，不影响复杂度量级。

解法：滑动窗口维护有效区间

核心思路

暴力是枚举所有起点，对每个长度为 k 的窗口重新数一遍元音，$O(nk)$。瓶颈很清楚：相邻两个窗口有 k - 1 个字符完全重合，却被重复统计了 k - 1 次。

观察这个重合关系：窗口从 [i-k, i-1] 移到 [i-k+1, i] 时，只有两个字符发生变化——右端进来一个 s[i]，左端出去一个 s[i-k]。中间部分的元音数没有任何变化。因此不需要重新数，只需要在计数器上做两次 $O(1)$ 的增减。

于是维护一个整数 count，写死它的含义并作为不变量：在处理完下标 i 之后，count 恰好等于子串 s[i-k+1 .. i] 中的元音个数。每轮循环通过「加入 s[i]、移除 s[i-k]」这一对操作把不变量从 i-1 维护到 i，代价 $O(1)$。

答案则是所有窗口的 count 的最大值。首窗口单独统计，随后每次右移恰好生成下一个起点对应的窗口，因此 n-k+1 个合法窗口不重不漏；对这些精确计数取最大值就是答案。窗口长度固定，不存在「窗口非法需要收缩」的情形：左右端点的距离恒为 k，左指针不需要独立维护，被移出的下标就是 i-k。

初始窗口需要单独构造：先把 s[0..k-1] 的元音数一次数完作为第一个 count，并用它初始化答案，然后主循环从 i = k 开始。这样写让主循环体保持整齐的「进一个、出一个、更新答案」三步，没有任何特判。

解题步骤

构造首个窗口：循环 i 从 0 到 k-1，把元音计入 count。这一步必须独立于主循环，因为下标小于 k 时不存在要移出的左端字符（i - k 会是负数）。用「先建首窗口、再滑动」代替「在主循环里判断 i >= k 才移出」，能省掉每轮一次分支判断，逻辑也更清晰。

用首个窗口初始化答案：answer = count。不能初始化为 0 然后只在主循环里更新——k == s.length() 时主循环一次都不进，答案就丢了。

主循环从 i = k 开始：此时窗口是 s[i-k+1 .. i]，右端点是 i。

先加入右端 s[i]，再移出左端 s[i-k]：两句都是无条件执行的独立判断，谁先谁后其实不影响结果（它们操作的是不同字符，加减可交换）。但移出的下标必须是 i - k 而不是 i - k + 1：新窗口的左边界是 i - k + 1，被挤出去的是它前面那一个，即 i - k。这是本题唯一的 off-by-one 陷阱。

更新答案：answer = max(answer, count)。放在两次增减之后，保证 count 描述的是完整的当前窗口。

返回 answer，不是 count（count 只是最后一个窗口的值），也不是窗口的起始下标。

以 s = "abciiidef"、k = 3 走一遍。元音集合是 {a, e, i, o, u}。

构造首窗口 [0, 2] 即 "abc"：a 是元音，b、c 不是，count = 1，answer = 1。

i = 3（字符 i）：右端 s[3] = 'i' 是元音，count = 2；左端移出 s[3-3] = s[0] = 'a'，是元音，count = 1。当前窗口 [1, 3] 即 "bci"，确实 1 个元音。answer 仍是 1。

i = 4（字符 i）：右端 'i' 元音，count = 2；移出 s[1] = 'b'，非元音，count 保持 2。窗口 [2, 4] 即 "cii"，2 个元音。answer = 2。

i = 5（字符 i）：右端 'i' 元音，count = 3；移出 s[2] = 'c'，非元音。窗口 [3, 5] 即 "iii"，3 个元音。answer = 3。

i = 6（字符 d）：右端非元音，count 保持 3；移出 s[3] = 'i' 元音，count = 2。窗口 [4, 6] 即 "iid"，2 个。answer 仍是 3。

i = 7（字符 e）：右端元音，count = 3；移出 s[4] = 'i' 元音，count = 2。窗口 [5, 7] 即 "ide"，2 个。answer 仍是 3。

i = 8（字符 f）：右端非元音，count 保持 2；移出 s[5] = 'i' 元音，count = 1。窗口 [6, 8] 即 "def"，1 个。

返回 3，对应窗口 "iii"。移出下标若写成 i - k + 1，维护的就不再是当前窗口；可用更小的反例 s = "ba"、k = 1 复现：滑到 "a" 时错误代码把刚加入的 a 又移出，返回 0 而不是 1。

代码实现

class Solution {
    public int maxVowels(String s, int k) {
        // 先把首个窗口 [0, k-1] 数满，主循环才能保持「进一个、出一个」的整齐结构。
        int count = 0;
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) {
                count++;
            }
        }
        // 必须用首窗口初始化答案，否则 k == n 时主循环不执行会漏掉唯一的窗口。
        int answer = count;

        for (int i = k; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) {
                count++;
            }
            // 新窗口左边界是 i-k+1，被挤出去的是它前面的 i-k。
            if (isVowel(s.charAt(i - k))) {
                count--;
            }
            answer = Math.max(answer, count);
        }
        return answer;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

func maxVowels(s string, k int) int {
	// 先把首个窗口 [0, k-1] 数满，主循环才能保持「进一个、出一个」的整齐结构。
	count := 0
	for i := 0; i < k; i++ {
		if isVowel(s[i]) {
			count++
		}
	}
	// 必须用首窗口初始化答案，否则 k == n 时主循环不执行会漏掉唯一的窗口。
	answer := count

	for i := k; i < len(s); i++ {
		if isVowel(s[i]) {
			count++
		}
		// 新窗口左边界是 i-k+1，被挤出去的是它前面的 i-k。
		if isVowel(s[i-k]) {
			count--
		}
		if count > answer {
			answer = count
		}
	}
	return answer
}

func isVowel(c byte) bool {
	return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
}

复杂度分析

时间复杂度：$O(n)$。构造首窗口扫描 k 个字符，主循环扫描剩下的 n - k 个字符，每个字符最多被「加入」一次、被「移出」一次，元音判定是 5 次比较的常数操作。总共 $O(n)$，与 k 无关——这正是相对 $O(nk)$ 暴力的全部收益。

空间复杂度：$O(1)$。只用了 count 和 answer 两个整数，没有开数组、没有做子串切分。若把元音判定改成哈希集合会额外占常数空间且常数更大，本题用 5 路比较即可。

关键点总结

定长窗口不需要独立的左指针：左边界恒等于 i - k + 1，被移出的字符恒是 s[i-k]。识别出「长度固定」这一条，就能把变长滑窗那套「while 收缩」的模板整个砍掉，代码短一半、也少一类死循环风险。

增量维护的前提是「贡献可加可减」：元音计数满足这个性质，所以窗口移动时只需两次 $O(1)$ 修正。遇到「窗口内最大值」这类不可减的统计量，就必须换成单调队列（239 题），这是面试常见的追问方向。

先建首窗口、再滑动优于「在主循环里判断 i >= k」：省一次分支，也让「用首窗口初始化答案」变得自然，顺手覆盖了 k == n 的边界。

移出下标是 i - k，不是 i - k + 1。自检方法是：答案必须落在 [0, k] 区间内，一旦超过 k 就说明移出逻辑写错了。

元音判定用固定的 5 路比较而不是集合查找。面试时若面试官把字符集扩大到需要动态配置，再升级成布尔表或哈希集合，说明「按需求选择数据结构」的判断力。

易错点总结

移出下标写成 i - k + 1：s = "ba"、k = 1 滑到第二个窗口时会把刚加入的 a 移出，返回 0 而不是 1；正确移出位置是 i - k。

answer 初始化为 0 而不是首窗口的 count：s = "aeiou"、k = 5 时主循环一次都不进，直接返回 0，正确答案是 5。

主循环从 i = 0 开始且没有独立构造首窗口：i < k 时 s.charAt(i - k) 的下标是负数，Java 抛越界、Go 直接 panic。

只加入右端忘记移出左端：count 变成整个前缀的元音数而不是窗口内的，s = "aeiou"、k = 2 会返回 5 而不是 2。

先更新答案再做加减：answer 会始终落后一个窗口。s = "bbbbae"、k = 2 的最后一个窗口 "ae" 才首次达到 2，错误顺序只会记录到前一个窗口的 1，返回 1 而不是 2。

返回 count 而不是 answer：s = "abciiidef"、k = 3 的最后一个窗口是 "def"，返回 1，而正确答案是 3。

在循环里用 s.substring(i-k+1, i+1) 重新统计：每轮都构造长度 k 的新串并重数一遍，时间退化回 $O(nk)$，$10^5$ 规模直接超时，同时还产生大量垃圾对象。

用 Set<Character> 且在循环内新建集合：每轮都分配一次集合，常数急剧放大；即使提到循环外，装箱比较也远慢于 5 次 char 比较。

误以为要找「至少 k 长度」或「最多 k 长度」的子串：改成可伸缩窗口后 s = "aeiou"、k = 2 会返回 5（整串），题目要的是恰好长度为 2 的窗口的最大值 2。

Go 里用 for i, c := range s 取字符：range 遍历字符串产出的是 rune 及其字节偏移，与后面 s[i-k] 的字节索引混用会在多字节字符下错位；本题限定小写字母虽不触发，但形成的习惯会在别的题上炸掉。

相似题目

题目	难度	考察点
643. 子数组最大平均数 I	简单	同为定长窗口，统计量换成和并要求返回浮点均值，注意精度与整型除法
1423. 可获得的最大点数	中等	取首尾两端的牌，需先把问题转化为「中间长度 `n-k` 的最小窗口和」
1052. 爱生气的书店老板	中等	定长窗口只负责统计「额外收益」，基础收益要单独累加后再相加
1151. 最少交换次数来组合所有的 1	中等	窗口长度由 1 的总数决定，答案是窗口内 0 的最小值而非最大值
209. 长度最小的子数组	中等	窗口长度不固定，必须引入独立左指针并在满足条件时主动收缩
3. 无重复字符的最长子串	中等	变长窗口 + 字符计数表，收缩条件由窗口内是否出现重复字符驱动