795. Number of Subarrays with Bounded Maximum

795. 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;
}