You are given an integer array nums and two integers minK and maxK.
A fixed-bound subarray of nums is a subarray that satisfies the following conditions:
The minimum value in the subarray is equal to minK.
The maximum value in the subarray is equal to maxK.
Return the number of fixed-bound subarrays.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].
Example 2:
Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.
Constraints:
2 <= nums.length <= 105
1 <= nums[i], minK, maxK <= 106
Solutions
Solution 1: Enumeration of Right Endpoint
From the problem description, we know that all elements of the bounded subarray are in the interval [minK, maxK], and the minimum value must be minK, and the maximum value must be maxK.
We traverse the array $nums$, count the number of bounded subarrays with nums[i] as the right endpoint, and then add all the counts.
The specific implementation logic is as follows:
Maintain the index $k$ of the most recent element not in the interval [minK, maxK], initially set to $-1$. Therefore, the left endpoint of the current element nums[i] must be greater than $k$.
Maintain the index $j_1$ of the most recent element with a value of minK, and the index $j_2$ of the most recent element with a value of maxK, both initially set to $-1$. Therefore, the left endpoint of the current element nums[i] must be less than or equal to $\min(j_1, j_2)$.
In summary, the number of bounded subarrays with the current element as the right endpoint is $\max(0, \min(j_1, j_2) - k)$. Add up all the counts to get the result.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.