10033. Count Subarrays Where Max Element Appears at Least K Times
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 least k times in that subarray.
A subarray is a contiguous sequence of elements within an array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
long long countSubarrays(vector<int>& A, int k) {
long long res = 0, ma = *max_element(begin(A), end(A));
vector<int> pos{-1};
for(int i = 0; i < A.size(); i++) if(A[i] == ma) pos.push_back(i);
pos.push_back(A.size());
for(int i = 1; i < pos.size() - 1; i++) {
long long l = i, r = i + k - 1;
if(r + 1 >= pos.size()) break;
long long lec = pos[l] - pos[l-1], ric = pos.back() - pos[r];
res += lec * ric;
}
return res;
}
};
|
