795. Number of Subarrays with Bounded Maximum #

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

Note:

• left, right, and nums[i] will be an integer in the range [0, 109].
• The length of nums will be in the range of [1, 50000].

Problem Summary #

Given an array A whose elements are all positive integers, and positive integers L and R (L <= R). Find the number of contiguous, non-empty subarrays whose maximum element is greater than or equal to L and less than or equal to R.

Solution Approach #

• The problem asks for subarrays whose maximum element lies in the range [L,R]. Suppose count(bound) calculates the number of subarrays in which all elements are less than or equal to bound. Then the answer to this problem can be transformed into count(R) - count(L-1).
• How do we count the number of subarrays whose elements are all less than bound? Use the variable count to record the number of consecutive elements to the left of bound that are less than or equal to bound. When such an element is found, the number of valid subarrays ending at this position is count + 1. When an element greater than B is encountered, the number of valid subarrays ending at this position is 0. res accumulates count in each round, and finally res stores the total number of subarrays that satisfy the condition.

Code #

package leetcode

func numSubarrayBoundedMax(nums []int, left int, right int) int {
	return getAnswerPerBound(nums, right) - getAnswerPerBound(nums, left-1)
}

func getAnswerPerBound(nums []int, bound int) int {
	res, count := 0, 0
	for _, num := range nums {
		if num <= bound {
			count++
		} else {
			count = 0
		}
		res += count
	}
	return res
}