795. Number of Subarrays with Bounded Maximum

Problem

Tags: Array, Two Pointers

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Example 2:

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= left <= right <= 10^9

Code

JS

// 795. Number of Subarrays with Bounded Maximum (11/20/53429)
// Runtime: 76 ms (82.35%) Memory: 42.82 MB (94.12%) 

/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var numSubarrayBoundedMax = function(nums, left, right) {
    // 儲存合法子陣列數、區間左界、區間右界
    let count = 0, left_index = -1, right_index = -1;
    
    // 遍歷 nums
    for(let i = 0; i < nums.length; i++) {
        // 該數超過最大可容忍值，截斷區間
        if(nums[i] > right) left_index = i;
        // 該數不小於最小可容忍值，向右推移區間右界
        if(nums[i] >= left) right_index = i;
        // 加上固定區間右界來看所有合法子陣列數
        count += right_index - left_index;
    }
    
    return count;
};