795. Number of Subarrays with Bounded Maximum

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

We are given an array nums of positive integers, and two positive integers left and right (left <= right).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least left and at most right.

Example:

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

Code

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int dp = 0;
        int prev = -1;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= left && nums[i] <= right) {
                dp = i - prev;
            }

            if (nums[i] > right) {
                dp = 0;
                prev = i;
            }

            if (nums[i] < left && i > 0) {
                dp = dp;
            }


            res += dp;
        }

        return res;
    }
}