2962. Count Subarrays Where Max Element Appears at Least K Times
Solved
Medium
Topics
Companies
You are given an integer array nums and a positive integer k.
Return the number of subarrays where the maximum element of nums appears at leas
t k times in that subarray.
A subarray is a contiguous sequence of elements within an array.
Example 1:
Input: nums = [1,3,2,3,3], k = 2
Output: 6
Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3
,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].
解法：
因为要找最大的数字
所以一开始就直接找会比较方便
然后再用1来表示的话也会比较方便
然后把经过的出现过的index记录下来
然后一定要出现k个以上的index
然后就可以利用纪录过的index
算出有几种子阵列可以那个了
姆咪
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k)
{
long long res = 0;
int maxn = 0;
int len = nums.size();
for(int i = 0 ; i < len ; i ++)
{
maxn = max(maxn,nums[i]);
}
vector<int> paper(len , 0);
for(int i = 0 ; i < len ; i ++)
{
if(nums[i] == maxn)
{
paper[i] = 1;
}
}
vector<int> save;
int r = 0 ;
for(; r < len ; r ++)
{
if(paper[r])
{
save.push_back(r);
}
if(save.size() >= k)
{
res += save[save.size() - k] + 1;
}
}
return res;
}
};