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