题目描述

给出一个正整数数组A和两个正整数L和R(L<=R)，寻找子数组，要求子数组连续、非空，且子数组内最大值的大小在[L, R]之间，求满足条件的子数组的个数。

样例

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

算法

复杂度 $O(n)$

我们只需要关注子数组中的最大值，那么满足要求的子数组中必须不能包含大于R的数字，且必须包含大小在[L, R]之间的数字。因此我们只需要关注这两类数字（大于R和大小在[L, R]之间）的位置。由于要求必须是连续子数组，因此只用子数组的最左元素和最右元素两个位置就能确定一个子数组。首先，遍历原始数组，一旦发现大于R的数字，说明我们一定不能包含这个数字，记录下这个数字的下标为l1，一旦发现在[L, R]之间的数字，说明我们需要包含这个数字，记录下这个下标为l2。

1) 在遇到下一个大于R的数字A[i]，这个数字下标为i，就可以看l2是否大于l1，如果大于则说明在下标(l1, i)之间的子数组满足要求，并且必须包含A[l2]，所以子数组的左边不能大于l2,可能的选择有l2-l1种，子数组的右边不能小于l2，可能的选择有i-l2种，所以在这个区间满足要求的子数组个数为(l2-l1)*(i-l2)。然后再更新l1的值变为i。

2) 在遇到下一个大小在[L, R]之间的数字A[i]，类似于上一种情况，只是变为更新l2的值为i即可。

注意在遍历结束后还要进行一次判断，end是A数组的结尾，判断是否在(l1, end)这个区间是否有满足条件的子数组。

时间复杂度分析：只需要遍历一遍A数组，复杂度为O(n)

C++ 代码

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int l1 = -1;
        int l2 = -1;
        int res = 0;
        for(int i = 0;i<A.size();i++){
            if(A[i]>R){
                if(l2>l1)
                    res += (l2-l1)*(i-l2);
                l1 = i;
            }
            if(A[i]<=R && A[i]>=L){
                if(l2>l1)
                    res+=(l2-l1)*(i-l2);
                l2 = i;
            }
        }
        if(l2>l1)//不要忘了遍历结束后再进行一次判断
            res+=(l2-l1)*(A.size()-l2);
        return res;
    }
};