题解 | #区间子数组个数#

import java.util.*;

/**
 * NC407 区间子数组个数
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型ArrayList
     * @param l int整型
     * @param r int整型
     * @return int整型
     */
    public int countSubarray (ArrayList<Integer> nums, int l, int r) {
        return solution(nums, l, r);
    }

    /**
     * 动态规划
     *
     * dp[i]表示以第i个元素为结尾的最大元素在[l,r]范围内的连续子数组个数
     *
     * 举例子找规律:
     * count表示当前元素前面连续小于l的元素个数
     *
     * [l,r] => [9,13]
     *         0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
     * nums       15 9  7  1  3  15 7  12 15 14 4  5  9  13
     * dp[i]   0  0  1  1  1  1  0  0  2  0  0  0  0  3  4
     * count   0  0  0  1  2  3  0  1  0  0  0  1  2  0  0
     *
     *         { dp[i-1]              , num<l
     * dp[i] = { dp[i-1] + 1 + count  , l<=num && num<=r
     *         { 0                    , num>r
     *
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int solution(ArrayList<Integer> nums, int l, int r){
        int n = nums.size();

        int[] dp = new int[n+1];
        int num;
        int count = 0;
        for(int i=1; i<=n; i++){
            num = nums.get(i-1);
            if(num < l){
                dp[i] = dp[i-1];
                count++;
            }else if(l<=num && num<=r){
                dp[i] = dp[i-1] + 1 + count;
                count = 0;
            }else{
                dp[i] = 0;
                count = 0;
            }
        }

        int result = 0;
        for(int i=1; i<=n; i++){
            result += dp[i];
        }

        return result;
    }
}