title
We are given an array A of positive integers, and two positive integers L and R (L <= R).
Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.
Example :
Input:
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
solution
求连续最长subarray, maximum in (L, R)区间，
count_valid记录以当前结尾的可用长度，wating记录每次小于L的累加。
static int Static_X = [](){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}();
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int ret = 0;
int count_valid = 0;
int count_waiting = 0;
for (auto& val : A) {
// Any number too high means all candidate subarrays can't satisfy!
if (val > R) {
count_valid = 0;
count_waiting = 0;
}
// Any number >= L means all current subarrays now satisfy
else if (val >= L) {
count_valid++;
ret += (count_valid + count_waiting);
count_valid += count_waiting;
count_waiting = 0;
}
// Any number too small means those already satisfying still do, and waiting still wait
else {
count_waiting++;
ret += count_valid;
}
}
return ret;
}
};
DP解法。。
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int res = 0, left = 0, sum = 0;
int cur;
for (int i = 0; i < A.size(); i++) {
int pre = A[i];
if (L <= pre && pre <= R) res++;
if (pre > R) continue;
cur = 0;
for (int j = i + 1; j < A.size(); j++) {
cur = max(A[j], pre);
if (L <= cur&&cur<= R) {
res++;
}
if (cur > R) break;
pre = cur;
}
}
return res;
}
};