Number of Subarrays with Bounded Maximum LT795

佚名 6年前 (2019-05-07) 随笔 1259人围观抢沙发百度已收录

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

Idea 1. Dynamic programming, count the number of subarrays end at current position i,

count = 0 if A[i] > R, move left = i

count = i - left if A[i] <= R && A[i] >= L, left is the last index A[left] > R or left = -1, it marks the bounary [left+1, i] has A[i] as valid maximum, it can form i - left subarrays, for example, [1, 1, 3, 2], when i = 2, left = -1, [1, 1, 3] can form subarrays: {3}, {1, 3}, {1, 1, 3}

count[i] = count[i-1] no change if A[i] < L

Time complexity: O(n)

Space complexity: O(1)

 1 class Solution {
 2     public int numSubarrayBoundedMax(int[] A, int L, int R) {
 3         int result = 0;
 4         int count = 0;
 5     
 6         for(int left = -1, right = 0; right < A.length; ++right) {
 7             if(A[right] > R) {
 8                 count = 0;
 9                 left = right;
10             }
11             else if(A[right] >= L) {
12                 count = right - left;
13             }
14             result += count;
15         }
16         return result;
17     }
18 }

Bruteforce, all pairs, Instead from ending element in the subarray, count the number of subarray staring at i and ending at right, store the maximum element, ++count if L <=maxSoFar >= R

Time complexity: O(n^2)

Space complexity: O(1)

class Solution {
    public int numSubarrayBoundedMax(int[] A, int L, int R) {
        int result = 0;
        int count = 0;
    
        for(int left = 0; left < A.length; ++left) {
            int maxSoFar = A[left];
            for(int right = left; right < A.length; ++right) {
                maxSoFar = Math.max(maxSoFar, A[right]);
                if(maxSoFar > R) {
                    break;
                }
                else if(maxSoFar >= L) {
                    ++count;
                } 
            }
        }
        
        return count;
    }
}