leetcode 2962. 统计最大元素出现至少 K 次的子数组 中等

给你一个整数数组 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 次。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= k <= 10^5

分析：可以用滑动窗口解决这道题。初始时，左端点 left 为 0。遍历 nums 数组，记录最大值 maxn 出现的次数。当 maxn 出现了 k 次时，说明从当前的 left 开始，一直到数组的最后，所有的子数组都符合条件。此时满足条件的子数组数量为 numsSize - right，right 是滑动窗口的右端点，也就是遍历的下标。之后开始移动左端点 left。如果 left 指向的值不是 maxn，说明仍然符合条件，此时 ans 要加上numsSize - right；否则不符合条件，可以开始继续移动 right。

long long countSubarrays(int* nums, int numsSize, int k) {int cnt=0,maxn=nums[0];long long ans=0;for(int i=1;i<numsSize;++i)maxn=fmax(maxn,nums[i]);for(int l=0,i=0;i<numsSize;++i){if(nums[i]==maxn)cnt++;if(cnt==k){ans+=numsSize-i;for(;l<=i;++l){if(nums[l]==maxn){l++,cnt--;break;}ans+=numsSize-i;}}// printf("l=%d i=%d cnt=%d ans=%lld\n",l,i,cnt,ans);}return ans;
}