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%