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

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

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

思路分析

解法一：滑动窗口（推荐）

核心思路：

维护长度为 k 的窗口，记录窗口内元音数量。

窗口右移时移除左端字符、加入右端字符。

取最大元音数量。

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(1)。

class Solution {
    public int maxVowels(String s, int k) {
        int count = 0;
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) {
                count++;
            }
        }
        int ans = count;

        for (int i = k; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) {
                count++;
            }
            if (isVowel(s.charAt(i - k))) {
                count--;
            }
            ans = Math.max(ans, count);
        }
        return ans;
    }

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

func maxVowels(s string, k int) int {
    count := 0
    for i := 0; i < k; i++ {
        if isVowel(s[i]) {
            count++
        }
    }
    ans := count

    for i := k; i < len(s); i++ {
        if isVowel(s[i]) {
            count++
        }
        if isVowel(s[i-k]) {
            count--
        }
        if count > ans {
            ans = count
        }
    }
    return ans
}

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

相似题目

题目	难度	考察点
643. 子数组最大平均数 I	简单	滑动窗口
1876. 长度为三且各字符不同的子字符串	简单	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口
76. 最小覆盖子串	困难	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/88154443