# 795. Number of Subarrays with Bounded Maximum

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].
``````

Note:

• L, R  and `A[i]` will be an integer in the range `[0, 10^9]`.
• The length of `A` will be in the range of `[1, 50000]`.

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int res = 0, n = A.size();
for (int i = 0; i < n; ++i) {
if (A[i] > R) continue;
int curMax = INT_MIN;
for (int j = i; j < n; ++j) {
curMax = max(curMax, A[j]);
if (curMax > R) break;
if (curMax >= L) ++res;
}
}
return res;
}
};
``````

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
return count(A, R) - count(A, L - 1);
}
int count(vector<int>& A, int bound) {
int res = 0, cur = 0;
for (int x : A) {
cur = (x <= bound) ? cur + 1 : 0;
res += cur;
}
return res;
}
};
``````

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int res = 0, left = -1, right = -1;
for (int i = 0; i < A.size(); ++i) {
if (A[i] > R) left = i;
if (A[i] >= L) right = i;
res += right - left;
}
return res;
}
};
``````

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int res = 0, left = -1, right = -1;
for (int i = 0; i < A.size(); ++i) {
if (A[i] > R) {
left = right = i;
continue;
}
if (A[i] >= L) right = i;
res += right - left;
}
return res;
}
};
``````

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/solution/

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/117585/Java-9-liner

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/117616/C++-O(n)-less10-lines

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/119162/Clean-and-simple-O(n)-Java

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation