LeetCode 2962 统计最大元素出现至少 K 次的子数组
🟠 中等偏上 https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/
思路
永远不要忘记分类的思想， 可以按右边结尾分类，那么以 i 结尾的合法子数组中一定包括k个最大值，左边的任意一个结束位置都是合法的。这样左边的界限是递增的，右边也是，时间复杂度：O(n)。
也可以以左边为分类标准，找到合法的位置后右边的每个位置都是合法的。
下面是以左分类，所以答案更新在while里面。
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
int max_one = INT_MIN;
for(int val:nums){
max_one = max(max_one,val);
}
long left = 0;
int count = 0;
long res = 0;
for(int i = 0;i<nums.size();i++){
if(nums[i]==max_one){
count++;
}
while(count>=k){
res+=nums.size()-i;
if(nums[left]==max_one){
count--;
}
left++;
}
}
return res;
}
};
上面是 左端点为left，右端点是数组结尾。也可以左边是数组开始，右边是i。
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
int max_one = INT_MIN;
for(int val:nums){
max_one = max(max_one,val);
}
long left = 0;
int count = 0;
long res = 0;
for(int i = 0;i<nums.size();i++){
if(nums[i]==max_one){
count++;
}
while(count>=k){
if(nums[left]==max_one){
count--;
}
left++;
}
res+=left;
}
return res;
}
};