分类
定长滑动窗口
定长滑动窗口
例题
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; } }
|