题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个字符串以及一个数字 k，要求找出长度为 k 的子串中元音最高的数字。

思路分享

  • 暴力解法就是遍历左右长度 k 的子串，同时遍历字串内，求得每个子串的元音个数，从而得出最大值。由于两层遍历，复杂度为 O(n^2)。

  • 本题可以采用定长滑动窗口，从而把复杂度降到 O(n)。

  • 所谓的滑动窗口由三个部分组成，加入、更新、退出。具体过程如下

  1. 加入，让下标为 i 元素进入窗口，如果 i 小于 k - 1 则重复这一步（重复的目的是初始化一个长为 k-1 的窗口）
  2. 更新，更新统计值（最大/最小）
  3. 退出，让下标 i-k+1 的元素离开窗口（也就是最左边那个），同时更新统计值

    https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/solutions/2809359/tao-lu-jiao-ni-jie-jue-ding-chang-hua-ch-fzfo/

代码解答（强烈建议自行解答后再看）

  • 滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maxVowels(string s, int k) {
        int result = 0;
        int yuan_count = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                yuan_count++;
            }

            if (i < k - 1) continue;

            result = max(result, yuan_count);

            if (result == k) break;

            char c = s[i-k+1];
           
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                yuan_count--;
            }
            
        }
        return result;
    }
};