Day 15: Monotonic Stack & Queue Problems
Recognize "next greater/smaller element" style problems and solve them in O(n) using a stack that only ever grows or shrinks monotonically.
Study
Concepts
Keep the stack sorted by popping violators
A monotonic stack maintains elements in strictly increasing (or decreasing) order at all times. When a new element would break that order, you pop everything that violates it BEFORE pushing the new element — and each pop is a resolved answer for the popped element (e.g. "this is your next greater element").
Each element is pushed once and popped at most once across the entire run, so even though there is a while-loop nested inside a for-loop, total work is O(n), not O(n²) — this amortized-analysis argument is worth stating explicitly in interviews.
Monotonic deque for sliding-window maximum
For "maximum in every window of size k", a monotonic decreasing deque (double-ended queue) stores INDICES, not values. Before pushing a new index, pop all indices from the back whose values are smaller (they can never be the max again while the new, larger element is in the window). Pop from the front when the front index falls outside the current window. The front of the deque is always the current window's maximum.
See It
Visualizations
Visualization
Next Greater Element for [2, 1, 2, 4, 3]
Pop everything smaller than the incoming number — each pop resolves that element's answer.
Monotonic Stack (indices, values shown)
4 (idx 3)
just pushed — nothing smaller left below it yet
2 (idx 2)
popped when 4 arrives → answer(2) = 4
1 (idx 1)
popped when 2 arrives → answer(1) = 2
Build It
Code Examples
Next Greater Element — O(n) monotonic decreasing stack
function nextGreaterElements(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // holds INDICES, values kept decreasing bottom to top
for (let i = 0; i < nums.length; i++) {
// Current number is a "next greater element" for anything smaller on the stack
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
const idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}
console.log(nextGreaterElements([2, 1, 2, 4, 3])); // [4, 2, 4, -1, -1]Sliding Window Maximum — O(n) monotonic deque
function maxSlidingWindow(nums, k) {
const deque = []; // indices, values kept decreasing front to back
const result = [];
for (let i = 0; i < nums.length; i++) {
// Drop indices that fell out of the window on the left
if (deque.length && deque[0] <= i - k) deque.shift();
// Drop smaller values from the back — they can't win while i is in range
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
deque.push(i);
if (i >= k - 1) result.push(nums[deque[0]]); // front = current max
}
return result;
}
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]Remember
Key Takeaways
- A monotonic stack pops "no longer useful" elements before pushing — each pop IS an answer for some earlier element.
- Amortized O(n): every index is pushed once and popped at most once, despite the nested-looking while loop.
- Trigger words: "next greater/smaller element", "daily temperatures", "largest rectangle in histogram".
- Monotonic deque stores indices (to know when an element falls outside the window), not just values.
- The front of a monotonic-decreasing deque is always the current window's max — O(1) to read.
Do It
Practice
- 1Solve "Daily Temperatures" (days until a warmer temperature) with a monotonic decreasing stack.
- 2Solve "Largest Rectangle in Histogram" — the hardest classic monotonic-stack problem; draw the stack state at each step on paper first.
- 3Convert the Sliding Window Maximum solution to also return the MINIMUM per window, using a monotonic increasing deque.