当前位置：首页 > article >正文

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

article 2025/2/11 1:27:22

一、题目

在这里插入图片描述

二、思路

2.1 解题思路

维护一个统计变量，出入时间窗口就判断

2.2 代码尝试

class Solution {
public:
    int maxVowels(string s, int k) {
        int sum=0;
        int maxsum=0;
        for(int i=0;i<k;i++){
            if(s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='o'||s[i]=='u'){
                sum++;
            }
        }
        maxsum=max(sum,maxsum);
        for(int i=k;i<s.size();i++){
            if(s[i-k]=='a'||s[i-k]=='e'||s[i-k]=='i'||s[i-k]=='o'||s[i-k]=='u'){
                sum--;
            }
            if(s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='o'||s[i]=='u'){
                sum++;
                maxsum=max(sum,maxsum);
            }
        }
        return maxsum;
    }
};

在这里插入图片描述

2.3 疑难问题

因为每次出入窗口都需要判断，所以时间复杂度会比较复杂，如何减少时间复杂度？

三、解法

class Solution {
public:
    bool isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; 
    }
    
    int maxVowels(string s, int k) {
        int n = s.size();
        int vowel_count = 0;
        for (int i = 0; i < k; ++i) {
            vowel_count += isVowel(s[i]);
        }
        int ans = vowel_count;
        for (int i = k; i < n; ++i) {
            vowel_count += isVowel(s[i]) - isVowel(s[i - k]);
            ans = max(ans, vowel_count);
        }
        return ans;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/solutions/518995/ding-chang-zi-chuan-zhong-yuan-yin-de-zu-4ka7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。