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

LeetCode算法题(Go语言实现)_15

article 2025/4/2 17:24:37

题目

给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的元音字母为（a, e, i, o, u）。

一、代码实现

func maxVowels(s string, k int) int {
    vowels := map[byte]bool{'a':true, 'e':true, 'i':true, 'o':true, 'u':true}
    maxCount, current := 0, 0
    
    // 初始化窗口
    for i := 0; i < k; i++ {
        if vowels[s[i]] {
            current++
        }
    }
    maxCount = current
    
    // 滑动窗口
    for i := k; i < len(s); i++ {
        // 移除左边字符
        if vowels[s[i-k]] {
            current--
        }
        // 添加右边字符
        if vowels[s[i]] {
            current++
        }
        // 更新最大值
        if current > maxCount {
            maxCount = current
        }
    }
    return maxCount
}

二、算法分析

1. 核心思路

滑动窗口策略：通过固定长度的窗口在字符串上滑动，每次仅需计算窗口两端字符对元音数量的影响，避免重复遍历
元音快速判断：使用哈希表存储元音字母，实现O(1)时间复杂度的查询操作

2. 关键步骤

初始化窗口：计算前k个字符中的元音数量
窗口滑动：
- 左边界字符退出时减少计数（若为元音）
- 右边界字符进入时增加计数（若为元音）
极值更新：实时记录窗口移动过程中的最大元音数

3. 复杂度分析

指标	值	说明
时间复杂度	O(n)	只需单次遍历字符串
空间复杂度	O(1)	仅需存储元音表和几个变量

三、图解示例

在这里插入图片描述

四、边界条件与扩展

1. 特殊场景处理

k=0：直接返回0（无有效窗口）
k > len(s)：返回整个字符串的元音数
全元音字符串：如"aeiou"，k=2时返回2

2. 多语言实现对比

语言	实现要点	性能优化技巧
Python	使用`collections.deque`实现滑动窗口	生成器表达式减少内存占用
Java	预处理元音索引数组`new boolean[256]`	位运算优化元音判断
C++	`std::unordered_set`存储元音，`std::max`实时比较	循环展开优化窗口滑动操作

3. 算法对比

方法	优点	缺点
滑动窗口法	时间复杂度O(n)，空间最优	需处理边界条件
前缀和法	支持随机区间查询	空间复杂度O(n)
暴力枚举	实现简单	时间复杂度O(nk)