力扣2444.统计定界子数组的数目

力扣2444.统计定界子数组的数目

• 观察到不满足条件的数 可以作为天然的分割线

  • 

  • 因此在枚举右端点的过程中 预处理minK，maxK和分割线上一次出现的下标

  • res += min(min_i,max_i) – i0;

  • 但是因为可能在到下个区段时 min_i和max_i尚未更新 导致结果为负数

  • 所以要跟0再取一个max

  • res += max(min(min_i,max_i)-i0,0)

• 方便计算

  • 初始化i0 = -1;

•   class Solution {
    public:
        long long countSubarrays(vector<int>& nums, int minK, int maxK) {
            long long res=0;
            int n = nums.size(),min_i = -1,max_i = -1,i0 = -1;
            for(int i=0;i<n;i++)
            {
                int x = nums[i];
                if(x == minK) min_i = i;
                if(x == maxK) max_i = i;
                if(x < minK || x > maxK) i0 = i;
                res += max(min(min_i,max_i)-i0,0);
            }
            return res;
        }
    };