Monotonic Stack and Queue
Maintain candidates in sorted order of value so next-greater and sliding-window extrema can be updated in linear time.
Monotonic Stack and Queue
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Monotonic stacks and monotonic queues are the ``throw away dominated candidates immediately'' tools. They show up in array problems where the answer depends on the nearest larger/smaller element or on the minimum/maximum inside a window.
When to Use It
Use them when:
candidates arrive in a fixed order,
once one candidate dominates another, the dominated one will never be useful again,
the query asks for a nearest blocker or for the best element in a moving window.
Core Idea
Keep indices in a stack or deque whose corresponding values stay monotone.
For nearest greater/smaller problems, the structure is usually a stack.
For sliding windows, it is usually a deque because indices leave from the front and dominated indices leave from the back.
Key Insight
Each index enters once and leaves once. The linear-time guarantee is not accidental; it comes from the dominance rule. If an index is popped, it is gone forever.
Worked Problem
Problem 1.
For every position \(i\), find the next position to the right whose value is strictly smaller.
Problem 2.
For every window of length \(k\), report its minimum.
Why monotonic structures fit.
In both problems, worse candidates can be discarded permanently:
a larger element cannot be the next smaller element for anyone once a smaller element appears before it,
an older larger element can never be the minimum of a future window if a newer smaller element is already inside.
Correctness Intuition
The invariant is the whole proof:
stack values stay monotone, so the first surviving candidate in the needed direction is the nearest valid one,
deque values stay monotone and indices stay increasing, so the front is always the best valid candidate inside the current window.
Complexity Analysis
Both the stack and deque versions run in \(O(n)\) time and \(O(n)\) memory.
Implementation
The code includes:
next strictly smaller element to the right,
sliding-window minimum.
Common Pitfalls
Choosing the wrong inequality and breaking ties incorrectly.
Storing values instead of indices, then losing window-expiration information.
Forgetting that some problems need strictly monotone order and others need non-strict order.
Variants / Extensions
Largest rectangle in histogram.
Monotone queue optimization in DP.
Cartesian tree construction from the same stack discipline.
Practice Problems
Next greater / next smaller element.
Sliding-window minimum or maximum.
Histogram and subarray-boundary problems driven by nearest blockers.
References
Code
Contest-ready reference implementation for the idea explained above.
vector<int> next_strictly_smaller_right(const vector<int>& a) {
int n = (int)a.size();
vector<int> answer(n, -1);
vector<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[i] < a[st.back()]) {
answer[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
return answer;
}
vector<int> sliding_window_minimum(const vector<int>& a, int k) {
deque<int> dq;
vector<int> answer;
for (int i = 0; i < (int)a.size(); ++i) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
dq.push_back(i);
if (i + 1 >= k) answer.push_back(a[dq.front()]);
}
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.