[leetcode]Number of Subarrays with Bounded Maximum by c++

Number of Subarrays with Bounded Maximum

We are given an array A of positive integers, and two positive integers L and R (L <= R).

给出非负整形数组 A,另给出两个非负整数 L,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.

返回 A 的子串中最大值在 L 和 R 区间的字符串的数量。

例子 :
给出:
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
分析: 这里有三个子串符合要求: [2], [2, 1], [3].
  • L, R  和 A[i] 范围为 [0, 10^9].

  • A 的长度限制在 [1, 50000] 区间内.


解题思路

第一种解法

稍微分析一下规律,如果给出的数组 A 全都在 L 和 R 之间,比如:

L = 1
R = 5
A [1,2,3,4,5]
容易得出,结果为 15,分别由数字的下标之和 1+2+3+4+5 得来。

当给出的 A 并不那么完美,当遇见不在左右区间的数字,此时便不需叠加下标,只需叠加当前数字距离最远区间数字的距离。
具体还是看代码理解吧,多写点例子,画一画就明白了。

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

            else if(A[i] >= L) right = i;

            sum += right - left;
        }
        return sum;
    }
};

山路元无雨,空翠湿人衣。