[leetcode] 795. Number of Subarrays with Bounded Maximum

Description

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:

1. L, R and A[i] will be an integer in the range [0, 10^9].
2. The length of A will be in the range of [1, 50000].

分析

• 看數組[2, 1, 4, 3]的最大值在[-∞, 4]範圍内的子數組的個數。當周遊到2時，隻有一個子數組[2]，周遊到1時，有三個子數組，[2], [1], [2,1]。當周遊到4時，有六個子數組，[2], [1], [4], [2,1], [1,4], [2,1,4]。當周遊到3時，有十個子數組。其實如果長度為n的數組的最大值在範圍[-∞, x]内的話，其所有子數組都是符合題意的，而長度為n的數組共有n(n+1)/2個子數組，剛好是等差數列的求和公式。
• 當周遊到的數字大于等于L時，right指派為目前位置i，那麼每次res加上right - left，随着right的不停自增1，每次加上的right - left，實際上也是一個等差數列。當A[i]大于R的時候，left = i，那麼此時A[i]肯定也大于等于L，于是rihgt=i，那麼right - left為0，相當于上面的cur重置為0的操作.

代碼

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int left=-1,right=-1;
        int res=0;
        for(int i=0;i<A.size();i++){
            if(A[i]>R) left=i;
            if(A[i]>=L) right=i;
            res+=right-left;
            
        }
        return res;
    }
};      

參考文獻