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

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 LeetCode 75 字节
标签
字符串 滑动窗口

题目描述

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

image-20260929084821138

image-20260929084821234

题意分析

枚举字符串中长度恰好为 k 的连续子串，统计每个子串中的元音字符数量，返回其中的最大值。元音只有小写的 a、e、i、o、u，同一个元音出现多次也要逐次计数。

窗口既不能短于 k，也不能为了多包含元音而加长。题目保证 1 <= k <= s.length，所以至少有一个完整窗口；没有元音时返回零，全是元音的窗口最多贡献 k。

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

核心思路

[!blue]

长度固定的相邻窗口有 k - 1 个字符相同，重新检查整个窗口会重复计算这些共有部分。只需保存当前窗口的元音数，向右移动一步时增加新进入字符的贡献，再减去离开字符的贡献。

先单独统计区间 [0, k - 1]，得到第一个完整窗口，并用它初始化答案。之后右端移动到下标 i 时，新进入的是 s[i]，离开的旧左端是 s[i - k]，更新后窗口范围恰好为 [i - k + 1, i]。

如果新字符是元音就加一，如果旧字符是元音就减一；非元音的贡献为零。完成这两步后，保留下来的公共部分计数没有变化，当前计数恰好对应新窗口，才能拿它更新最大值。

右端从 k 扫到末尾，会不重不漏地枚举剩余全部窗口。k 等于字符串长度时，后续循环不执行，但首窗口已经计算并计入答案，不需要特殊分支。

解题步骤

  1. 统计前 k 个字符中的元音数，保存为当前计数 count。
  2. 用 count 初始化答案，先覆盖第一个完整窗口。
  3. 从下标 i = k 开始，当前字符是元音则增加计数。
  4. 下标 i - k 的移出字符是元音则减少计数。
  5. 用完成加减后的计数更新最大值，扫描结束返回答案。

代码实现

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 次，后面每次移动只检查两个字符。
  • 空间复杂度：O(1)。只记录当前计数和最大计数，元音集合大小固定。

关键点总结

[!green]

  • 固定长度窗口向右一步只有一进一出，公共部分无需重算。
  • 移出位置是 i - k，更新后的新左端才是 i - k + 1。
  • 首窗口单独初始化后，唯一窗口和末尾窗口都会被正常统计。

易错点总结

[!yellow]

  • 只加入新字符不移出旧字符：会统计不断增长的前缀，而不是长度固定的子串。
  • 减去新左端的字符：真正离开窗口的是它前一位 i - k，错减会破坏计数。
  • 在一进一出未完成时更新答案：此时计数可能暂时包含 k + 1 个字符，不能当作完整合法窗口。
  • 答案初始为零且只统计后续移动：k == n 时唯一的首窗口会被漏掉。
  • 返回最后窗口计数：最佳窗口可能更早出现，需要保存全局最大值。

相似题目

题目 难度 关联与区别
643. 子数组最大平均数 I 简单 把元音映射为1、其他字符映射为0，就可用定长窗口求最大和。
1100. 长度为 K 的无重复字符子串 中等 同样枚举长度k窗口，原题检查频次不重复，本题累计元音指示值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/88154443
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！