Monotonic Queue

Sliding window min/max in O(1) amortized using the two-stack queue pattern.

[Data Structures]|

Jul 9, 2026

|explanatory_notes.md|

#monotonic-queue#sliding-window#deque#min-max

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

int combine(int a, int b) { return max(a, b); }
const int IDENTITY = INT_MIN;

struct MonoStack {
    vector<int> st, agg;
    MonoStack() { agg.push_back(IDENTITY); }
    void push(int x) { st.push_back(x); agg.push_back(combine(agg.back(), x)); }
    int pop() { int r = st.back(); st.pop_back(); agg.pop_back(); return r; }
    int top() { return st.back(); }
    int query() { return agg.back(); }
    bool empty() { return st.empty(); }
    int size() { return st.size(); }
};

struct MonoQueue {
    MonoStack s1, s2;
    void push(int x) { s2.push(x); }
    void pop() {
        if (s1.empty()) while (!s2.empty()) s1.push(s2.pop());
        s1.pop();
    }
    int front() {
        if (s1.empty()) while (!s2.empty()) s1.push(s2.pop());
        return s1.top();
    }
    int query() {
        if (s1.empty()) return s2.query();
        if (s2.empty()) return s1.query();
        return combine(s1.query(), s2.query());
    }
    bool empty() { return s1.empty() && s2.empty(); }
    int size() { return s1.size() + s2.size(); }
};

36 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Monotonic Queue

Maintains the aggregate (min/max) of a sliding window in $O(1)$ amortized using two monotonic stacks.

How It Works

Two stacks:

S_1

(output) and

S_2

(input)

push(x) appends to

S_2

while tracking the running aggregate

pop() removes from

S_1

; when

S_1

is empty, all of

S_2

transfers to

S_1

(reversal preserves order)

Each stack tracks its own aggregate. Overall aggregate =

\text{op}(S_1.\text{agg}, S_2.\text{agg})

When to Use

Sliding window minimum/maximum

Any queue that needs aggregate queries (min, max, gcd, etc.)

Notes

Change combine() for different operations: min for sliding min, max for sliding max, __gcd for sliding gcd

Complexity

Push / Pop —

O(1)

amortized

Query —

O(1)

Space —

O(n)