[LeetCode] 每日一题 2444. 统计定界子数组的数目（滑动窗口）

题目描述

给你一个整数数组 nums 和两个整数 minK 以及 maxK 。

nums 的定界子数组是满足下述条件的一个子数组：

• 子数组中的 最小值 等于 minK 。

• 子数组中的 最大值 等于 maxK 。

返回定界子数组的数目。

子数组是数组中的一个连续部分。

题目链接

https://leetcode.cn/problems/count-subarrays-with-fixed-bounds

示例输入

示例 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 的位置 lastMinIndex

• 当前窗口内最后一次出现 maxK 的位置 lastMaxIndex

• 当前窗口内不能出现小于 minK 或大于 maxK 的非法元素，否则整个窗口要重新开始。

每次当 lastMinIndex 和 lastMaxIndex 都有效时，说明以当前 right 结尾的子数组中，合法子数组的起点可以从 left 到 min(lastMinIndex, lastMaxIndex)，于是更新答案。

这个方法是标准的“边移动边结算”模式，用滑动窗口把区间性的问题高效处理掉。

代码实现

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long ans = 0;
        int n = nums.length;
        int left = 0, lastMinIndex = -1, lastMaxIndex = -1;
        for (int right = 0; right < n; right++) {
            int num = nums[right];
            if (num > maxK || num < minK) {
                left = right + 1;
                lastMaxIndex = -1;
                lastMinIndex = -1;
            }
            if (num == maxK) {
                lastMaxIndex = right;
            }
            if (num == minK) {
                lastMinIndex = right;
            }
            if (lastMaxIndex != -1 && lastMinIndex != -1) {
                ans += Math.min(lastMaxIndex, lastMinIndex) - left + 1;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)

  • 遍历一遍数组，所有指针移动、状态更新均是常数时间

• 空间复杂度：O(1)

  • 除了若干变量外，没有使用额外空间，空间开销是常数

总结

这道题依然是滑动窗口的经典应用，不过相较于常规窗口，这里需要维护子数组中特定元素的位置，同时实时更新答案。
整体思路清晰简单，非常适合用来训练 滑动窗口+区间动态信息维护 的思考方式，特别适合一遍过关。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。