结合实例是最好理解的
参考,结合一道leetcode 2962题,难度中等,题目描述如下:
给你一个整数数组 nums 和一个 正整数 k 。
请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组,并返回满足这一条件的子数组的数目。
子数组是数组中的一个连续元素序列。
示例1
输入:nums = [1,3,2,3,3], k = 2
输出:6
解释:包含元素 3 至少 2 次的子数组为:[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。
示例2
输入:nums = [1,4,2,1], k = 3
输出:0
解释:没有子数组包含元素 4 至少 3 次
那么滑动窗口是怎么作用的?
我的理解,滑动窗口,本质也是双指针的一种
我们设置2个指针,left
和right
,都从坐标0
开始出发
对于上题中,要求最大数至少出现k次,我们设置计数器cntmx为0
, 获取数组最大值为mx
,然后:
-
right
指针从0开始右移,遇到nums[right] == mx
时,cntmx++
; - 当
cntmx == k
时,right
停止右移,left
开始右移,直到nums[left] == mx
时停止,cntmx--
; - 设置
ans = 0
,每次left
停止后,说明左边有left
种可能,ans += left
- 重复上述过程,直至数组全部遍历
时间复杂度O(n)
,空间复杂度O(1)
上代码:
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
int mx = *max_element(nums.begin(), nums.end()); //获取个最大值先
int n = nums.size();
int left = 0, right = 0;
int cntmx = 0;
long long ans = 0; //这个是我们要返回的结果
for (;right < n; right++){
if (nums[right] == mx) cntmx++;
while (cntmx >= k){ //这里其实==就可以
if (nums[left] == mx) cntmx--;
left++; //先判断left是不是,再++,因为left是从0开始的,注意边界问题
}
ans += left; //向右遍历,右边的可能性已经沿着遍历方向遍历完了,只考虑叠加左边的所有可能情况
}
return ans;
}
};