795. Number of Subarrays with Bounded Maximum

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.

1
2
3
4
5
6
7
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].

题目大意

求最大值 >= L<= R的所有子序列。

解题思路

通过 > R 将数组分割成多个子序列。
再通过 < L 将数组分割计算,确保每个子序列中都存在至少一个满足 >= L && <= R

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
var ans = 0
var lastIndex = 0
for (i, a) in (A+[R+1]).enumerated() {
if a > R {
let c = i - lastIndex
var last = 0
for (j, subA) in A[lastIndex..<i].enumerated() {
if subA >= L {
ans += (j - last + 1) * (c - j)
last = j + 1
}
}
lastIndex = i + 1
}
}
return ans
}
}
0%