目标
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：
- 子数组中的 最小值 等于 minK 。
- 子数组中的 最大值 等于 maxK 。
返回定界子数组的数目。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。示例 2：
输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。说明：
- 2 <= nums.length <= 10^5
- 1 <= nums[i], minK, maxK <= 10^6
思路
统计满足条件的子数组个数，子数组中必须包含 minK 和 maxK，并且其它元素值在 [minK, maxK] 内。
明显的滑动窗口问题，求窗口内 minK 和 maxK 的计数均大于等于 1 且元素值在 [minK, maxK] 内的子数组个数。
如果遇到不在范围内的元素，直接从下一个位置重新开始滑动，关键点是记录滑动的开始位置 start。
代码
/**
* @date 2025-04-26 0:25
*/
public class CountSubarrays2444 {
public long countSubarrays(int[] nums, int minK, int maxK) {
int n = nums.length;
int minCnt = 0, maxCnt = 0;
int left = 0, start = 0;
long res = 0L;
for (int right = 0; right < n; right++) {
if (nums[right] < minK || nums[right] > maxK) {
left = right + 1;
start = left;
minCnt = 0;
maxCnt = 0;
continue;
}
if (nums[right] == minK) {
minCnt++;
}
if (nums[right] == maxK) {
maxCnt++;
}
while (minCnt > 0 && maxCnt > 0) {
if (nums[left] == minK) {
minCnt--;
}
if (nums[left] == maxK) {
maxCnt--;
}
left++;
}
res += left - start;
}
return res;
}
}
性能
