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]
.
Rust Solution
struct Solution;
impl Solution {
fn num_subarray_bounded_max(a: Vec<i32>, l: i32, r: i32) -> i32 {
let n = a.len();
let mut start = 0;
let mut end = 0;
let mut res = 0;
for i in 0..n {
if a[i] > r {
start = i + 1;
}
if a[i] >= l {
end = i + 1;
}
if start < end {
res += end - start;
}
}
res as i32
}
}
#[test]
fn test() {
let a = vec![2, 1, 4, 3];
let l = 2;
let r = 3;
let res = 3;
assert_eq!(Solution::num_subarray_bounded_max(a, l, r), res);
}
Having problems with this solution? Click here to submit an issue on github.