题目分析
本题要求在给定字符串中找到长度为 k 的子串,使其包含的元音字母(a,e,i,o,u)数量最多。这是一个典型的固定窗口大小的滑动窗口问题。
解题思路
- 初始化元音数量:
-
- 先计算字符串前 k 个字符中的元音数量作为初始值
- 滑动窗口处理:
-
- 从第 k 个字符开始向右移动窗口:
-
-
- 加入当前字符:如果是元音,计数加1
- 移除窗口左侧字符:如果是元音,计数减1
-
-
- 每次移动后更新最大元音数量
- 元音判断优化:
-
- 使用逻辑或判断字符是否为元音(简单高效)
完整代码
public class LeetCode1456 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine().trim();
int k = Integer.parseInt(br.readLine().trim());
System.out.println(new Solution().maxVowels(s, k));
}
static class Solution {
public int maxVowels(String s, int k) {
// 1. 获取字符串长度(边界条件:k=0的情况由题目约束可忽略)
int n = s.length();
// 2. 初始化第一个窗口的元音数量
String vowels = "aeiou";
int vowelCount = 0;
for (int i = 0; i < k; i++) {
if (vowels.contains(s.charAt(i) + "")) {
vowelCount++;
}
}
int maxVowels = vowelCount; // 当前最大元音数
// 3. 滑动窗口处理(窗口范围:[i-k, i-1] → [i-k+1, i])
for (int i = k; i < n; i++) {
// 移除窗口左侧元素(位置:i-k)
char leftChar = s.charAt(i - k);
if (vowels.contains(leftChar + "")) {
vowelCount--;
}
// 添加窗口右侧元素(位置:i)
char rightChar = s.charAt(i);
if (vowels.contains(rightChar + "")) {
vowelCount++;
}
// 更新最大值
maxVowels = Math.max(maxVowels, vowelCount);
}
return maxVowels;
}
}
}
知识点分类
- 滑动窗口算法:
-
- 固定窗口大小的经典应用
- 通过加减操作实现O(n)时间复杂度
- 字符串处理:
-
- 字符遍历与条件判断
- 索引边界处理(避免数组越界)
- 性能优化:
-
- 避免重复计算(元音判断函数抽取)
- 单次遍历完成计算
- 边界条件处理:
-
- 自动兼容 k=1 或 k=字符串长度的情况
- 处理输入长度为1的特殊情况