LeetCode 795. Number of Subarrays with Bounded Maximum

原题链接在这里：https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/

题目：

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 <= 105
• 0 <= nums[i] <= 109
• 0 <= left <= right <= 109

题解：

When iterate to current num, if num > right, then the subarray ending with num is not valid. set prev = i + 1.

If num is within [left, right], then we find a valid subarray ending with num, the start index of subarray is prev. Accumlate the count i - prev + 1 to the result.

Time Complexity: O(n). n = nums.length.

Space: O(1).

AC Java:

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

跟上Count Subarrays With Fixed Bounds.