LeetCode 795. Number of Subarrays with Bounded Maximum

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2018/03/07/LeetCode-795-Number-of-Subarrays-with-Bounded-Maximum/

访问原文「LeetCode 795. Number of Subarrays with Bounded Maximum」

题目要求

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

题意解析

现在有一个A正整数数组，两个正整数L和R，其中L <= R。
求满足下面要求的子数组数量：子数组中的最大数介于L和R之间。

解法分析

首先以大于R数进行分段，分段不包含大于R的数。
然后对每一段进行遍历。假设某段遍历到的数字为M，位于这一段的i位置，如果L<=M<=R，子数组数量加上i+1；如果M<L，从这个数字向前遍历，假设遍历到的第一个介于L和R之间的数字为N，位于这一段的j位置，子数组数量加上j+1。

解题代码

public int numSubarrayBoundedMax(int[] A, int L, int R) {
    if (null == A || A.length <= 0) {
        return 0;
    }
    int sum = 0;
    List<Integer> numSet = new ArrayList<>();
    for (int i : A) {
        if (i <= R) {
            numSet.add(i);
        } else {
            sum = getSum(L, R, sum, numSet);
            numSet.clear();
        }
    }
    sum = getSum(L, R, sum, numSet);
    return sum;
}

private int getSum(int L, int R, int sum, List<Integer> numSet) {
    for (int j = 0; j < numSet.size(); j++) {
        if (numSet.get(j) >= L && numSet.get(j) <= R) {
            sum += j + 1;
        } else {
            for (int k = j - 1; k >= 0; k--) {
                if (numSet.get(k) >= L && numSet.get(k) <= R) {
                    sum += k + 1;
                    break;
                }
            }
        }
    }
    return sum;
}