力扣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;}};