# 795. Number of Subarrays with Bounded Maximum

[**795. Number of Subarrays with Bounded Maximum**](https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/)

Given an integer array `nums` and two integers `left` and `right`, return *the number of contiguous non-empty **subarrays** such that the value of the maximum array element in that subarray is in the range* `[left, right]`.

The test cases are generated so that the answer will fit in a **32-bit** integer.

**Example 1:**

```
Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
```

**Example 2:**

```
Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7
```

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 109`
* `0 <= left <= right <= 109`

**My Solutions:**

* 方法1：和560类似，可以用暴力解法，遍历每一个subarray。有些直接超出范围的可以省略

```
public int numSubarrayBoundedMax(int[] nums, int L, int R) {
    int N = nums.size();
    int res = 0;
    for (int i = 0; i < N; i++) {
        if (nums[i] > R) continue; // 超出范围，跳过
        int curMax = -1; // 也可以用最小数 
        for (int j = i; j < N; j++) {
            curMax = max(curMax, A[j]);
            if (curMax > R) break;
            if (curMax >= L) res++;
        }
    }
    return res;
}
```

* 方法2：

看数组\[2, 1, 4, 3]的最大值在\[-∞, 4]范围内的子数组的个数。

* 遍历到2时，只有一个子数组\[2]
* 遍历到1时，有三个子数组，\[2], \[1], \[2,1]
* 遍历到4时，有六个子数组，\[2], \[1], \[4], \[2,1], \[1,4], \[2,1,4]
* 遍历到3时，有十个子数组，\[2], \[1], \[4], \[3],\[2,1], \[1,4], \[4,3],\[2,1,4],\[1,4,3],\[2,1,4,3]

如果长度为n的数组的最大值在范围\[-∞, x]内的话，其所有子数组都是符合题意的，而长度为n的数组共有n(n+1)/2个子数组，是等差数列的求和公式。所以在遍历数组的时候，如果当前数组小于等于x，则cur自增1，然后将cur加到结果res中；如果大于x，则cur重置为0。这样可以正确求出最大值在\[-∞, x]范围内的子数组的个数。

只需要用最大值在\[-∞, R]范围内的子数组的个数，减去最大值在\[-∞, L-1]范围内的子数组的个数，即可得到最大值在\[L, R]范围内的子数组的个数

```
public int numSubarrayBoundedMax(int[] A, int L, int R) {
        return count(A, R) - count(A, L - 1);
}

public int count(int[] A, int bound) {
    int res = 0, cur = 0;
    for (int x : A) {
        cur = (x <= bound) ? cur + 1 : 0;
        res += cur;
    }
    return res;
}
```

* 方法3：理念和方法2类似

使用left和right来分别标记子数组的左右边界，使得其最大值在范围\[L,R]内

* 当A\[i]大于等于L时，right赋值为当前位置i，那么每次res加上right - left，随着right的不停自增1，每次加上的right - left，实际上也是一个等差数列
* 当A\[i]大于R的时候，left = i，right=i，那么right - left为0，相当于上面的cur重置为0的操作

```
public int numSubarrayBoundedMax(int A, int L, int R) {
    int res = 0, left = -1, right = -1;
    for (int i = 0; i < A.size(); ++i) {
        if (A[i] > R) {
            left = right = i;
            continue;
        }
        if (A[i] >= L) right = i;
        res += right - left;
    }
    return res;
}
```