Description
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 <= 1051 <= nums[i], minK, maxK <= 106
Solutions
Solution 1: Enumerate the Right Endpoint
According to the problem description, we know that all elements of a bounded subarray are within the range [minK, maxK], and the minimum value must be minK, while the maximum value must be maxK.
We iterate through the array nums and count the number of bounded subarrays with nums[i] as the right endpoint. Then, we sum up all the counts.
The specific implementation logic is as follows:
- Maintain the index k of the most recent element that is not within the range [minK, maxK], initialized to -1. The left endpoint of the current element nums[i] must be greater than k.
- Maintain the most recent index j1 where the value is minK and the most recent index j2 where the value is maxK, both initialized to -1. The left endpoint of the current element nums[i] must be less than or equal to min(j1, j2).
- Based on the above, the number of bounded subarrays with the current element as the right endpoint is max\bigl(0,\ min(j1, j2) - k\bigr). Accumulate all these counts to get the result.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
class Solution: def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int: j1 = j2 = k = -1 ans = 0 for i, v in enumerate(nums): if v < minK or v > maxK: k = i if v == minK: j1 = i if v == maxK: j2 = i ans += max(0, min(j1, j2) - k) return ans(code-box)
