number-of-subarrays-with-bounded

给定一个包含正整数的数组A , 以及两个正整数 L 和R (L <= R).

返回最大元素值在范围[L, R]之间的子数组(连续, 非空)的个数,

number-of-subarrays-with-bounded-maximum

样例

样例 1:

输入: A = [2, 1, 4, 3], L = 2, R = 3
输出: 3
解释: 有三个子数组满足要求：[2], [2, 1], [3].

样例 2:

输入: A = [7,3,6,7,1], L = 1, R = 4
输出: 2

思路1  O(N^2)、遍历数组 设置一个 max 值，在遍历数组 取出最大值，如果当前 a[j] > r 跳出循环，如果 a[j] >== l result++, 整体思想有点 dp 的感觉


思路2  O(N)、遍历数组，记录下符合位置的索引 index ，和不符合位置的索引 temp ，result += index - temp 

public class Solution {
    /**
     * @param a: an array
     * @param l: an integer
     * @param r: an integer
     * @return: the number of subarrays such that the value of the maximum array element in that subarray is at least l and at most R
     */
    public int numSubarrayBoundedMax(int[] a, int l, int r) {
        // Write your code here
        int result = 0;
        for (int i = 0; i < a.length; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < a.length; j++) {
                max = Math.max(max, a[j]);
                if (max > r) {
                    break;
                }
                if (max >= l) {
                    result++;
                }
            }
        }
        return result;
    }
}

public class Solution {
   
    /**
     * @param a: an array
     * @param l: an integer
     * @param r: an integer
     * @return: the number of subarrays such that the value of the maximum array element in that subarray is at least l and at most R
     */
    public int numSubarrayBoundedMax(int[] a, int l, int r) {
        // Write your code here
        int result = 0;
        int index = -1;
        int temp = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > r) {
                index = temp = i;
                continue;
            }
            if (a[i] >= l) {
                index = i;
            }
            result += index - temp;
        }
        return result;
    }

}

GitHub： https://github.com/xingfu0809/Java-LintCode