Sliding windows again

Jimmy (xiaoke) Shen
2 min readJul 3, 2023

2762. Continuous Subarrays

2762. Continuous Subarrays

It was the 3rd question of the weekly 352 code competition of LC . The key trick is finding the min/max value in a sliding window. I had a previous post Sliding window min/max, priority queue & Monotonic Queue.

Multiset

This has the time complexity of O(n log n)

class Solution {
public:
long long continuousSubarrays(vector<int>& nums) {
long long ret = 0;
const int n = nums.size();
multiset<int> windows;
for (int i = 0, j = 0; j < n; ++j){
windows.insert(nums[j]);
while (*windows.rbegin() - *windows.begin() > 2){
windows.erase(windows.find(nums[i++])); // no need check whether exist as we know it does exist
}
ret += j - i + 1;
}
return ret;
}
};

Monotonic Queue

This one has the complexity of O(n).

class Solution {
public:
long long continuousSubarrays(vector<int>& nums) {
long long ret = 0;
const int n = nums.size();
deque<int> find_min_dq, find_max_dq;
auto &dq1 = find_min_dq;
auto &dq2 = find_max_dq;
for (int i = 0, j = 0; j < n; ++j){
//Use the fresh minimum val to replace the old ones. Maintain an increasing queue.
while (!dq1.empty() && nums[dq1.back()] >= nums[j]){
dq1.pop_back();
}
while (!dq2.empty() && nums[dq2.back()] <= nums[j]){
dq2.pop_back();
}
dq1.push_back(j);dq2.push_back(j);
while (nums[dq2.front()] - nums[dq1.front()] > 2){
i++;
while (dq1.front() < i)dq1.pop_front();
while (dq2.front() < i)dq2.pop_front();
}
ret += j - i + 1;
}
return ret;
}
};

Priority Queue with soft deletion

This one has the complexity of O(n log n).

typedef pair<int, int> PII;
class Solution {
public:
long long continuousSubarrays(vector<int>& nums) {
long long ret = 0;
const int n = nums.size();
priority_queue<PII, vector<PII> , greater<PII>> min_heap;
priority_queue<PII> max_heap;
for (int i = 0, j = 0; j < n; ++j){
min_heap.emplace(nums[j], j);max_heap.emplace(nums[j], j);
while (max_heap.top().first - min_heap.top().first > 2){
i ++;
while (max_heap.top().second < i)max_heap.pop(); // soft deletion
while (min_heap.top().second < i)min_heap.pop();
}
ret += j - i + 1;
}
return ret;
}
};

--

--