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