# 795. Number of Subarrays with Bounded Maximum 区间子数组个数

@TOC

## # 题目描述

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].

## # 解题方法

### # 动态规划

1. A[i] < L 这个情况，以A[i]为结尾的子数组的最大值没有改变，因此dp[i] = dp[i - 1]
2. A[i] > R 此时，以A[i]为结尾的子数组的最大值已经大于了R，所以dp[i] = 0.把这个位置设定为新的开始，记录该位置为prev.
3. L <= A[i] <= R 从prev到i之间的任意起始位置到i的子数组都满足题目条件，因此dp[i] = i - prev.

``````class Solution(object):
def numSubarrayBoundedMax(self, A, L, R):
"""
:type A: List[int]
:type L: int
:type R: int
:rtype: int
"""
if not A: return 0
dp = [0] * len(A)
prev = -1
for i, a in enumerate(A):
if a < L and i > 0:
dp[i] = dp[i - 1]
elif a > R:
dp[i] = 0
prev = i
elif L <= a <= R:
dp[i] = i - prev
return sum(dp)
``````

``````class Solution(object):
def numSubarrayBoundedMax(self, A, L, R):
"""
:type A: List[int]
:type L: int
:type R: int
:rtype: int
"""
dp = 0
res = 0
prev = -1
for i, a in enumerate(A):
if a < L and i > 0:
res += dp
elif a > R:
dp = 0
prev = i
elif L <= a <= R:
dp = i - prev
res += dp
return res
``````

### # 暴力搜索+剪枝

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
const int N = A.size();
int res = 0;
for (int i = 0; i < N; ++i) {
if (A[i] > R) continue;
int curMax = INT_MIN;
for (int j = i; j < N; ++j) {
curMax = max(curMax, A[j]);
if (curMax > R) break;
if (curMax >= L) ++res;
}
}
return res;
}
};
``````

### # 线性遍历

count函数很好设计，因为只需要线性遍历一次，就知道了。每次遍历的时候，如果当前的值小于等于bound，那么就等于在前面的子数组上又加上了一个新的数组。所以我们需要一个变量来保存前面的数组有多少个了。

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
return count(A, R) - count(A, L - 1);
}
int count(vector<int>& A, int bound) {
int res = 0, cur = 0;
for (int x : A) {
cur = (x <= bound) ? cur + 1 : 0;
res += cur;
}
return res;
}
};
``````

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
const int N = A.size();
int res = 0;
int left = -1, right = -1;
for (int i = 0; i < N; ++i) {
if (A[i] > R) left = i;
if (A[i] >= L) right = i;
res += right - left;
}
return res;
}
};
``````

## # 日期

2018 年 9 月 14 日 —— 现在需要的还是夯实基础，算法和理论 2018 年 12 月 16 日 —— 周赛好难