Description#
Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Example 2:
Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= left <= right <= 109
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
| class Solution:
def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
def f(x):
cnt = t = 0
for v in nums:
t = 0 if v > x else t + 1
cnt += t
return cnt
return f(right) - f(left - 1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
return f(nums, right) - f(nums, left - 1);
}
private int f(int[] nums, int x) {
int cnt = 0, t = 0;
for (int v : nums) {
t = v > x ? 0 : t + 1;
cnt += t;
}
return cnt;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
auto f = [&](int x) {
int cnt = 0, t = 0;
for (int& v : nums) {
t = v > x ? 0 : t + 1;
cnt += t;
}
return cnt;
};
return f(right) - f(left - 1);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func numSubarrayBoundedMax(nums []int, left int, right int) int {
f := func(x int) (cnt int) {
t := 0
for _, v := range nums {
t++
if v > x {
t = 0
}
cnt += t
}
return
}
return f(right) - f(left-1)
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
n = len(nums)
l, r = [-1] * n, [n] * n
stk = []
for i, v in enumerate(nums):
while stk and nums[stk[-1]] <= v:
stk.pop()
if stk:
l[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and nums[stk[-1]] < nums[i]:
stk.pop()
if stk:
r[i] = stk[-1]
stk.append(i)
return sum(
(i - l[i]) * (r[i] - i) for i, v in enumerate(nums) if left <= v <= right
)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
int n = nums.length;
int[] l = new int[n];
int[] r = new int[n];
Arrays.fill(l, -1);
Arrays.fill(r, n);
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
int v = nums[i];
while (!stk.isEmpty() && nums[stk.peek()] <= v) {
stk.pop();
}
if (!stk.isEmpty()) {
l[i] = stk.peek();
}
stk.push(i);
}
stk.clear();
for (int i = n - 1; i >= 0; --i) {
int v = nums[i];
while (!stk.isEmpty() && nums[stk.peek()] < v) {
stk.pop();
}
if (!stk.isEmpty()) {
r[i] = stk.peek();
}
stk.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (left <= nums[i] && nums[i] <= right) {
ans += (i - l[i]) * (r[i] - i);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int n = nums.size();
vector<int> l(n, -1);
vector<int> r(n, n);
stack<int> stk;
for (int i = 0; i < n; ++i) {
int v = nums[i];
while (!stk.empty() && nums[stk.top()] <= v) stk.pop();
if (!stk.empty()) l[i] = stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; ~i; --i) {
int v = nums[i];
while (!stk.empty() && nums[stk.top()] < v) stk.pop();
if (!stk.empty()) r[i] = stk.top();
stk.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (left <= nums[i] && nums[i] <= right) {
ans += (i - l[i]) * (r[i] - i);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| func numSubarrayBoundedMax(nums []int, left int, right int) (ans int) {
n := len(nums)
l := make([]int, n)
r := make([]int, n)
for i := range l {
l[i], r[i] = -1, n
}
stk := []int{}
for i, v := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] <= v {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
l[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i-- {
v := nums[i]
for len(stk) > 0 && nums[stk[len(stk)-1]] < v {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
r[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
for i, v := range nums {
if left <= v && v <= right {
ans += (i - l[i]) * (r[i] - i)
}
}
return
}
|
