2444. Count Subarrays With Fixed Bounds
给定一个阵列 nums 跟两个整数 minK、maxK，
求有多少种 subarray 的最小值等于 minK 且最大值等于 maxK。
(subarray 是由 array 中一段连续的元素组成)
Example 1:
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation:
[1,3,5] 和 [1,3,5,2] 这两个 subarray 满足最大值是 5 且最小值是 2
Example 2:
Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation:
总共有 10 种 subarray，每一种都满足最大值是 1 且最小值是 1
解题思路:
给的阵列大小最大到 10^5，一些 O(n^2) 的做法应该不会过，
要用一些 O(nlogn) 以下的做法来做，
其中一个作法是 sliding windows 可以做到线性时间。
用 L、R 来维护当前的区间 nums[L~R]，
当 nums[R] < minK 或 nums[R] > maxK 时，
因为符合条件的 subarray 不可能包含 nums[R]，
所以可以处理完 nums[L+1~R-1], nums[L+2~R-1], ..., nums[R-1~R-1] 后，
跳过 nums[R] 从 nums[R+1~R+1] 开始。
但是要快速的知道 nums[L~R-1] 有多少个答案，
我们必须要知道从哪个位置开始是答案，
假设 nums[L~i] 是答案则 nums[L~i], nums[L~i+1], ..., nums[L~R-1] 都会是答案，
因为 nums[i~R-1] 的元素全部都介于 [minK, maxK] (前面有检查过的关系)，
就可以快速求得 nums[L~R-1] 这个区间的答案数量为 R-i。
我们还需要快速求得这个 i 是多少，
从 L 开始，i = max(下一个等于 minK 的位置, 下一个等于 maxK 的位置)，
可以用两个 queue 来记录等于 minK 的元素位置跟等于 maxK 的元素位置，
当 R 右移时检查是否符合并 push 进 queue，
并且两个 queue 都不为空时则 nums[L~R] 也是符合条件的答案，
当 L 右移时检查是否超过 queue 的 front，如果超过则 pop，
并处理上述的过程。
C++ code:
class Solution {
public:
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
long long ans = 0;
queue<int> minidx, maxidx;
int l = 0, r = 0;
while(l < nums.size()){
if(r == nums.size() || nums[r] > maxK || nums[r] < minK){
l++;
if(l <= r){
if(minidx.size() > 0 && minidx.front() < l) minidx.pop();
if(maxidx.size() > 0 && maxidx.front() < l) maxidx.pop();
if(minidx.size() > 0 && maxidx.size() > 0){
int idx = max(minidx.front(), maxidx.front());
ans += r - idx;
}
}
else r++;
}
else if(r < nums.size()){
if(nums[r] == minK) minidx.push(r);
if(nums[r] == maxK) maxidx.push(r);
if(minidx.size() > 0 && maxidx.size() > 0) ans++;
r++;
}
}
return ans;
}
};