分类
定长滑动窗口
定长滑动窗口
例题
1456. 定长子串中元音的最大数目
1343. 大小为 K 且平均值大于等于阈值的子数组数目
643. 子数组最大平均数 I
题解和思路
定长滑窗的思路可以分成三步：
- 进窗口 2. 更新答案 3.出窗口。
例题：
1456. 定长子串中元音的最大数目
入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
更新：更新答案。一般是更新最大值/最小值。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量。
需要特别注意的是，这个思路是在循环中保证了长度为K的窗口，进和出在一起发生，因此更新答案在进和出的中间。
思路很简单，当不满足长度时持续进入窗口，满足长度的 时刻 来记录和更新答案，然后（对于下一轮循环会多出的项）移除
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
28
29
30
31
32
33
| class Solution {
public int maxVowels(String s, int k) {
int left = 0, right = 0;
Set<Character> vowelSet = new HashSet<>();
vowelSet.add('a');
vowelSet.add('e');
vowelSet.add('i');
vowelSet.add('o');
vowelSet.add('u');
int count = 0;
int ret = 0;
char[] stochar = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
char inChar = stochar[i];
if (vowelSet.contains(inChar)) {
count++;
}
if (i < k - 1) {
continue;
}
ret = Math.max(count, ret);
char outChar = stochar[i - k + 1];
if (vowelSet.contains(outChar)) {
count--;
}
}
return ret;
}
}
|
（也可以使用left, right）或者先处理窗口再移动
1343. 大小为 K 且平均值大于等于阈值的子数组数目
同样的思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int numOfSubarrays(int[] arr, int k, int threshold) {
int count = 0;
int n = arr.length;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (i < k - 1) {
continue;
}
if (sum / k >= threshold) {
count++;
}
sum -= arr[i - k + 1];
}
return count;
}
}
|
643. 子数组最大平均数 I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
double avg = -10e4;
int sum = 0;
for (int i = 0; i < n; i++) {
int num = nums[i];
sum += num;
if (i < k - 1) {
continue;
}
avg = Math.max(avg, (double) sum / k);
sum -= nums[i - k + 1];
}
return avg;
}
}
|
