日期: 2025 年 4 月 26 日

目标

给你一个整数数组 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;
    }

}

性能