【Leetcode 每日一题】2962. 统计最大元素出现至少 K 次的子数组

问题背景

给你一个整数数组 $nums$ 和一个 正整数 $k$。
请你统计有多少满足 「$nums$ 中的 最大 元素」至少出现 $k$ 次的子数组，并返回满足这一条件的子数组的数目。
子数组是数组中的一个连续元素序列。

数据约束

• $1\le nums.length\le 10^5$
• $1\le nums[i]\le 10^6$
• $1\le k\le 10^5$

解题过程

子数组长度越大，最大元素出现次数越有可能满足条件，适用滑窗。
累计答案时有两种思路，在内层循环中，可以固定左端点，当前右端点直到数组末尾都是合法的答案，共有 $(n-right)$ 个；在内层循环结束时，可以固定右端点，数组开头直到当前左端点都是合法的答案，共有 $left$ 个。

具体实现

class Solution {public long countSubarrays(int[] nums, int k) {long res = 0;int target = 0;for (int num : nums) {target = Math.max(target, num);}int count = 0;for (int left = 0, right = 0; right < nums.length; right++) {if (nums[right] == target) {count++;}while (count >= k) {if (nums[left] == target) {count--;}                left++;// 在内层循环中统计答案，固定左端点得到的所有子数组都是符合条件的res += n - right;}// 在内层循环结束时统计答案，固定右端点得到的所有子数组都是符合条件的// res += left;}return res;}
}