# Sliding windows again

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