Monotonic Queue Concepts

Summary

Usually, the monotonic queue can be used in the following situations.

1. Next Greater/Greatest: find the first larger or smaller element (or the largest or smallest element) from the current index to the very right index;
2. Sliding Window Max: find the smallest or largest value in a sliding window
3. Length s.t. Max: find the longest interval of an element so that the element is the largest or smallest value in the interval (this is essentially nearest larger, since the current number will be the maximum until it meets the nearest larger number)

Other experience is that,

1. Pop elements on one side because once the current element join in, the element poped could not be the maximum (or minimum) values later
2. Pop elements on the other side because of the invalid index (out of sliding window or poped from the normal queue)

We provide some templates for typical usage of Monotonic Queue.

// Sliding Window from left to right
struct SlidingWindowMax {
    // {index, val}
    deque<pair<int, int>> dq; 
    // invalidate x where x <= index
    void remove(int index) {
        while (dq.size() > 0 && dq.front().first <= index) {
            dq.pop_front();
        }
    }
    void add(int index, int val) {
        while (dq.size() > 0 && dq.back().second <= val) {
            dq.pop_back();
        }
        dq.push_back({index, val});
    }
    pair<int, int> max() {
        return dq.size() > 0 ? dq.front() : -1;
    }
};

// Sliding Window from left to right
struct SlidingWindowNearestHigher {
    // {index, val}
    deque<pair<int, int>> dq; 
    // invalidate x where x <= index
    void remove(int index) {
        while (dq.size() > 0 && dq.front().first <= index) {
            dq.pop_front();
        }
    }
    void add(int index, int val) {
        while (dq.size() > 0 && dq.back().second <= val) {
            dq.pop_back();
        }
        dq.push_back({index, val});
    }
    pair<int, int> max() {
        return dq.size() > 0 ? dq.back() : -1;
    }
};