LWC 74: 795. Number of Subarrays with Bounded Maximum
Problem:
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].
思路： 先关注一波性质，在L和R之间的最大值val符合 val in [L, R]， 可以转为：求区间内的任意值x ， x in [L, R]。所以，把数组的每个位置当作起点，如A = [2, 1, 4, 3]:
代码语言：javascript复制位置0： [2], [2, 1], [2, 1, 4], [2, 1, 4, 3]
位置1： [1], [1, 4], [1, 4, 3]
位置2： [4], [4, 3]
位置3： [3]
for each subset in each position:
calculate whether the last value in subset <= R
你会发现，考虑位置0，subset[2, 1, 4]中的last value 4时，因为4 > R，所以删除该subset，且连同位置1，2，3中包含4的子集可以一并删除。代码如下：
代码语言：javascript复制 public int numSubarrayBoundedMax(int[] A, int L, int R) {
return count(A, R) -count(A, L - 1);
}
int count(int[] a, int r) {
int ret = 0;
int cnt = 0;
for (int v : a) {
if (v <= r) cnt ;
else cnt = 0;
ret = cnt;
}
return ret;
}Python版本：
代码语言：javascript复制class Solution(object):
def numSubarrayBoundedMax(self, A, L, R):
"""
:type A: List[int]
:type L: int
:type R: int
:rtype: int
"""
def count(A, R):
ret = cnt = 0
for v in A:
cnt = cnt 1 if v <= R else 0
ret = cnt
return ret
return count(A, R) - count(A, L - 1)
