795.number of Subarrays With Bounded Maximum

Description Link to heading

795. Number of Subarrays with Bounded Maximum (Medium) 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⁵
• 0 <= nums[i] <= 10⁹
• 0 <= left <= right <= 10⁹

Solution Link to heading

Monotone stack Link to heading

When we encounter problems concerning the maximum value within a continuous interval, the application of a monotonic stack is worth considering.

For nums[idx], we aim to determine the quantity of subarrays where nums[idx] is the maximum value. Let lidx be the largest l that satisfies nums[l] >= nums[idx] and l < idx; let ridx be the smallest r that satisfies nums[r] > nums[idx] and r > idx. Our task is to enumerate all idx that satisfy 0 <= idx < n, find the corresponding lidx and ridx, and thereby calculate the quantity of subarrays.

The quantity of subarrays equals (ridx - idx) * (idx - lidx)

In this problem, we can consider using a stack that decreases monotonically from the bottom to the top to find ridx and lidx. Note that the elements in the stack are indices idx. When enumerating i, if nums[i] > nums[stk.top()], for idx = stk.top(), pop the top element of the stack, ridx = i, lidx is the new top of the stack, if the stack is empty, then lidx = -1.

After enumerating i, for the remaining elements in the stack, idx = stk.top(), ridx = n, pop the elements in the stack, if the stack is empty, lidx = -1, otherwise lidx = stk.top();.

Code Link to heading

Monotone stack Link to heading

class Solution {
  public:
    int numSubarrayBoundedMax(vector<int> &nums, int left, int right) {
        int res = 0;
        stack<int> stk;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && nums[i] > nums[stk.top()]) {
                int idx = stk.top();
                int len1 = i - idx;
                int val = nums[idx];
                stk.pop();
                int len2 = stk.empty() ? idx + 1 : idx - stk.top();
                if (val <= right && val >= left) {
                    res += len1 * len2;
                }
            }
            stk.push(i);
        }
        while (!stk.empty()) {
            int idx = stk.top();
            int len1 = n - idx;
            int val = nums[idx];
            stk.pop();
            int len2 = stk.empty() ? idx + 1 : idx - stk.top();
            if (val <= right && val >= left) {
                res += len1 * len2;
            }
        }
        return res;
    }
};