当前位置：首页 > news >正文

6207. 统计定界子数组的数目(每日一难phase3-2)

news 来源：原创 2024/5/6 5:40:50

6207. 统计定界子数组的数目显示英文描述

给你一个整数数组 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 <= 1e5
1 <= nums[i], minK, maxK <= 1e6

解析：

看到连续子序列往往会想到滑动窗口
可以想象一下，如果一个数 nums[i] < minK || nums[i] > maxK, 那么所有的区间都不会包含这个数，这个数就成了一个屏障，将左右两端的数分开；
例如： nums = [1,3,5,2,7,5,1,2,3], minK = 1, maxK = 5 ；7这个元素就将左右两侧分开，我们只需要求解两侧对应区间数之和即可；
如果一个区间包含minK,maxK 且所有数满足minK，maxK范围时，我们才会计算区间，区间长度如何计算呢？（下图为以cur为结尾的区间长度）
flag初始值为-1，如果遇到屏障，将flag更新为 cur ，l = -1，r = -1(表示最大值还没遇到)
将以每个元素结尾区间数相加就是所有区间数；

代码：

class Solution {
public:
    // 滑动窗口
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        // 记录最大，最小位置
        int l=-1,r=-1,flag=-1;
        int n=nums.size();
        long long res=0;
        for(int i=0;i<n;i++){
            // 当前数加入，更新最大值最小值
            // 相当于滑动窗口，窗口右移
            if(nums[i]>=maxK){
                r=i;
            }
            if(nums[i]<=minK){
                l=i;
            }
            // 越界
            if((r!=-1&&nums[r]>maxK)||(l!=-1&&nums[l]<minK)){
                l=-1;
                r=-1;
                flag=i;
            // 如果最大值最小值没有全部遇到
            }else if(l==-1||r==-1){
                continue;
            }
            // 当前数符合，计算区间大小
            else if(nums[l]==minK&&nums[r]==maxK){
                res+=min(l,r)-flag;
            }
        }
        return res;
    }
};