题目

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

示例

示例 1：

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。

示例 2：

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3：

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。

示例 4：

输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。

示例 5：

输入：s = "tryhard", k = 4
输出：1

代码实现思路

第一次写的，理解错了定长滑动窗口的实现，导致无法界定窗口的结尾而致使遍历不完全，时间复杂度也达到了O(nk)，但整体思路是正确的

public static int maxVowels(String s, int k) {
        int maxV = -1;
        int count = 0;
        char[] cs = s.toCharArray();
        for (int i = 0,j=k-1; j < s.length()-k ; i++,j++) {
            int x = i,y = j;
            int nextStar = x + k;
            while(x <= y){
               if (cs[x] == 'a' || cs[x] == 'e' || cs[x] == 'i' || cs[x] == 'o' || cs[x] == 'u'){
                   count++;
                   nextStar = x ;
               }
               x++;
            }
            maxV = Math.max(maxV,count);
            i = nextStar;
            j = nextStar + k;
        }
        return maxV == -1 ? 0 : maxV;
    }

看了别人的思路后，初步理解了滑动窗口的实现.

其实滑动窗口并不是真的在数组上界定一个窗口实体，而是逻辑上的窗口。

例如这道题，只需单指针顺序遍历数组即可，所谓窗口只是一个表达式而已（例：s[i - k + 1]），满足表达式的下标即执行离开窗口或进入窗口，而离开进入也并非真正意义上的input/output，而是对结果集进行更新，一切操作以结果集为导向，都是逻辑意义上的操作...

public static int maxVowels2(String S, int k) {
        char[] s = S.toCharArray();
        int ans = 0;
        int vowel = 0;
        for (int i = 0; i < s.length; i++) {
            // 1. 进入窗口
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                vowel++;
            }
            if (i < k - 1) { // 窗口大小不足 k
                continue;
            }
            // 2. 更新答案
            ans = Math.max(ans, vowel);
            // 3. 离开窗口
            char out = s[i - k + 1];
            if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
                vowel--;
            }
        }
        return ans;
    }

总结

此类定长滑动窗口都可以使用以下三部法解决：

入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
更新：更新答案。一般是更新最大值/最小值。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量。

以上三步适用于所有定长滑窗题目。