795. Number of Subarrays with Bounded Maximum

We are given an array nums of positive integers, and two positive integers left and right (left <= right).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least left and at most right.

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

Note:

  • leftright, and nums[i] will be an integer in the range [0, 109].
  • The length of nums will be in the range of [1, 50000].
class Solution {
    public int numSubarrayBoundedMax(int[] n, int l, int r) {
        int j = 0, res = 0, count = 0;
        for(int i = 0; i < n.length; i++) {
            if(n[i] >= l && n[i] <= r) {
                res += i - j + 1;
                count = i - j + 1;
            }
            else if(n[i] < l) res += count;
            else {
                j = i + 1;
                count = 0;
            }
        }
        return res;
    }
}

2 pointers, j是合格subarray的起始点,count是目前为止的合格的subarray的长度,如果当前数字合格,就更新count和res。

如果数字小于l,说明这个数不合格,但是前面的subarray仍然有可能合格,加上count。

如果数字大于r,说明都用不了,重置j和count。

上一篇:LeetCode91. 解码方法


下一篇:最大子数组和