2444. Bounded Subarrays

Count Subarrays With Fixed Bounds

又是一个有够适合掌握滑动窗口的好题

既然要minK和maxK两路Bounded

那我们每次挪动窗口右尾的rightIdx时

先检查一下是否$minK \leq nums[rightIdx] \leq maxK$

没做到的话 代表$nums[rightIdx]$摔出既定范围

由rightIdx做窗口右尾的合规子数组肯定不存在

于是把窗口左端leftIdx改成rightIdx + 1

同时prevMinIdx和prevMaxIdx都重置到-1

因为还不知道$nums[leftIdx:]$有没有刚好是$minK$或$maxK$的元素

只要$nums[leftIdx: rightIdx + 1]$没谁掉出界

那我们就看这扇窗口中

最近一次做到$nums[i] = minK$的索引$i$

把prevMinIdx赋予给$i$

最近一次做到$nums[j] = maxK$的索引$j$

把prevMaxIdx赋予给$j$

一旦prevMinIdx跟prevMaxIdx都不是-1

就来到了我们窗口凑齐题目要求的瞬间

本窗口能切的子数组有三个条件要遵守：

(1). 右尾在rightIdx

(2). 左端起码要有leftIdx 且不超过右尾

(3). 左端再大也得在min(prevMinIdx, prevMaxIdx)封顶

(1)和(2)非常直观 重点在于(3)是怎么来的

如果窗口内某个索引$k$符合min(prevMinIdx, prevMaxIdx) $< k$

那么$nums[k:rightIdx + 1]$必然没法同时拥有$minK$和$maxK$

题目要我们的子数组一起抓$minK$和$maxK$才行

于是当前窗口内 符合条件的子数组

有$C =$ min(prevMinIdx, prevMaxIdx) + 1 - leftIdx这么多

把$C$加入最终要回传的boundedSubarraysCount

C++

#include <vector>
using namespace std;

long long countBoundedSubarrays(vector<int>& nums, int minK, int maxK) { // LeetCode Q.2444.
    long long boundedSubarraysCount = 0;

    int prevMinIdx = -1, prevMaxIdx = -1;

    int leftIdx = 0;
    for (int rightIdx = 0; rightIdx < nums.size(); rightIdx++) {
        int num = nums[rightIdx];

        if (num < minK || num > maxK) { // Reset.
            prevMinIdx = -1, prevMaxIdx = -1;
            leftIdx = rightIdx + 1;
            continue;
        }

        if (num == maxK)
            prevMaxIdx = rightIdx;
        if (num == minK)
            prevMinIdx = rightIdx;

        if (min(prevMinIdx, prevMaxIdx) >= 0)
            boundedSubarraysCount += min(prevMinIdx, prevMaxIdx) + 1 - leftIdx;
    }

    return boundedSubarraysCount;
}

Python

def count_bounded_subarrays(nums: list[int], min_k: int, max_k: int):  # LeetCode Q.2444.
    bounded_subarrays_count = 0

    prev_min_idx, prev_max_idx = -1, -1

    left_idx = 0
    for right_idx, num in enumerate(nums):
        if num < min_k or num > max_k:  # Reset.
            prev_min_idx, prev_max_idx = -1, -1
            left_idx = right_idx + 1
            continue

        if num == max_k: prev_max_idx = right_idx
        if num == min_k: prev_min_idx = right_idx

        if min(prev_min_idx, prev_max_idx) >= 0:
            bounded_subarrays_count += min(prev_min_idx, prev_max_idx) + 1 - left_idx

    return bounded_subarrays_count

时间复杂度$O(n)$ 其中$n$是输入的数组长度

空间则是$O(1)$ 仅需四根指针 和负责记录总值的boundedSubarraysCount