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
Awill be in the range of[1, 50000].
给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。
求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。
例如 : 输入: A = [2, 1, 4, 3] L = 2 R = 3 输出: 3 解释: 满足条件的子数组: [2], [2, 1], [3].
注意:
- L, R 和
A[i]都是整数，范围在[0, 10^9]。 - 数组
A的长度范围在[1, 50000]。
Runtime: 256ms
Memory Usage: 19.6 MB 1 class Solution {
2 func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
3 var res:Int = 0
4 var left:Int = -1
5 var right:Int = -1
6 for i in 0..<A.count
7 {
8 if A[i] > R
9 {
10 left = i
11 right = i
12 continue
13 }
14 if A[i] >= L
15 {
16 right = i
17 }
18 res += right - left
19 }
20 return res
21 }
22 }
Runtime: 288 ms Memory Usage: 19.6 MB
1 class Solution {
2 func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
3 var first = 0,second = 0
4 var result = 0,rangeCount = 0
5
6 while second < A.count && first < A.count {
7 if A[second] >= L && A[second] <= R {
8 result += (second - first + 1)
9 rangeCount = second - first + 1
10 } else if (A[second] < L) {
11 result += rangeCount
12 } else { // A[second] > R
13 first = second + 1
14 rangeCount = 0
15 }
16 second += 1
17 }
18 return result
19 }
20 }
300ms
1 class Solution {
2 func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
3 var result = 0
4 var numberOfLows = 0
5 var numberOfEquals = 0
6 enum Status {
7 case equal
8 case low
9 case high
10 }
11 var status = Status.equal
12
13 for (_, value) in A.enumerated() {
14 switch status {
15 case .equal:
16 if value < L {
17 numberOfLows = 1
18 numberOfEquals += 1
19 } else if value > R {
20 result += numberOfSubarrayInLength(numberOfEquals)
21 numberOfEquals = 0
22 } else {
23 numberOfEquals += 1
24 }
25 case .low:
26 if value < L {
27 numberOfLows += 1
28 numberOfEquals += 1
29 } else if value > R {
30 result += numberOfSubarrayInLength(numberOfEquals)
31 numberOfEquals = 0
32 result -= numberOfSubarrayInLength(numberOfLows)
33 numberOfLows = 0
34 } else {
35 numberOfEquals += 1
36 result -= numberOfSubarrayInLength(numberOfLows)
37 numberOfLows = 0
38 }
39 case .high:
40 if value < L {
41 numberOfLows = 1
42 numberOfEquals = 1
43 } else if value > R {
44
45 } else {
46 numberOfLows = 0
47 numberOfEquals = 1
48 }
49 }
50 if value < L {
51 status = .low
52 } else if value > R {
53 status = .high
54 } else {
55 status = .equal
56 }
57 }
58 result -= numberOfSubarrayInLength(numberOfLows)
59 result += numberOfSubarrayInLength(numberOfEquals)
60 return result
61 }
62
63 func numberOfSubarrayInLength(_ n: Int) -> Int {
64 if n <= 0 {
65 return 0
66 }
67
68 return n * (n + 1) / 2
69 }
70 }
356ms
1 class Solution {
2 func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
3 var count = 0
4 for i in 0..<A.count {
5 var currMax = A[i]
6 for j in i..<A.count {
7 currMax = max(currMax, A[j])
8 if currMax >= L && currMax <= R {
9 count += 1
10 } else if currMax > R {
11 break
12 }
13 }
14 }
15 return count
16 }
17 }
3816ms
1 class Solution {
2 func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
3 if A.count <= 0 { return 0 }
4 var cursor = 0
5 var count = 0
6 while cursor < A.count {
7 for i in cursor ..< A.count {
8 let temp = A[cursor...i]
9 let max = temp.max()!
10 if max > R {
11 break
12 }
13 if max >= L {
14 count += 1
15 }
16 }
17 cursor += 1
18 }
19 return count
20 }
21 }