LeetCode 2444. 统计定界子数组的数目
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：
- 子数组中的 最小值 等于
minK。 - 子数组中的 最大值 等于
maxK。
返回定界子数组的数目。
子数组是数组中的一个连续部分。
思路
双指针算法，每次固定右边去计算有多少个合法的左端点。遍历 nums，记录 minK 最近出现的位置 minI，以及 maxK 最近出现的位置 maxI，当遍历到 nums[i] 时，如果 minK 和 maxK 都遇到过，则左端点在 [0,min(minI,maxI)] 中的子数组，包含 minK 和 maxK，最小值一定是 minK，最大值一定是 maxK。我们需要额外记录在 [minK,maxK] 范围之外的最近元素位置，记作 i0 此时总的合法个数为 min(minI,maxI) - i0
代码
class Solution {
public:
using ll = long long;
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
ll ans = 0;
int min_i=-1,max_i=-1,i0=-1;
for(int i=0;i<nums.size();i++){
int x = nums[i];
if(x==minK){
min_i = i;
}
if(x==maxK){
max_i = i;
}
if(x<minK || x>maxK){
i0 = i;
}
ans += max(min(min_i,max_i) - i0, 0);
}
return ans;
}
};
