For each number in an array, find the next greater number to its right, or -1 if there is none. Do it in O(n).

Use a stack of indexes whose values are decreasing from bottom to top. For each number, while the stack is not empty and the top's value is smaller than the current number, pop it and record the current number as its answer. Then push the current index. Numbers left on the stack at the end have no greater number, so their answer is -1. Every index is pushed once and popped at most once, so time is O(n) and memory is O(n).

Given daily temperatures, return for each day how many days you must wait for a warmer one (0 if never).

Keep a stack of day indexes with decreasing temperatures. For each day, pop every earlier day that is colder and set its answer to today minus that day's index. Then push today. Days left on the stack get 0. Because each day is pushed and popped at most once the time is O(n), and memory is O(n) in the worst case of falling temperatures.

Return the maximum of every window of k consecutive numbers in an array, in O(n).

Use a deque of indexes whose values decrease from front to back. For each new number, pop indexes from the back while their value is less than or equal to the new number, because they can never be a maximum while the new number is in the window. Push the new index. If the front index has left the window, pop it from the front. Once the first window is full, the front of the deque is that window's maximum. Each index enters and leaves the deque once, so time is O(n) and memory is O(k).

Given the heights of bars in a histogram, find the area of the largest rectangle that fits inside it.

Keep a stack of bar indexes with increasing heights. For each bar, while the top of the stack is taller than the current bar, pop it. That popped bar's rectangle cannot extend further right than here. Its left edge is just after the new top of the stack, or index 0 if the stack is empty, so its width is the current index minus the left edge. Track the largest area. Process an extra bar of height 0 at the end to flush the stack. Time is O(n) and memory is O(n).

Monotonic Stack and Queue

intermediate · 30 min · Asked often · Last reviewed 29 Oct 2026 · by TheLearningLoop Team

Key takeaways

A monotonic stack keeps its items in sorted order. Before pushing a new item, pop every item that would break the order. Each popped item has just found its answer.
Every item is pushed once and popped at most once, so a nested-looking loop is still O(n) overall.
Use a stack for "next greater or smaller element" and "largest rectangle". Use a monotonic queue (a deque) for "maximum of every sliding window".
The classic signal is a question about the nearest bigger or smaller neighbour, or about a maximum or minimum over a moving window.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use a monotonic stack or queue

Use a monotonic stack when you have:

A question about the nearest bigger or smaller neighbour: "next greater element", "next warmer day", "stock span".
A largest rectangle question, such as the biggest rectangle in a histogram or in a grid of 1s.
A need to match or nest things where a new item makes earlier items obsolete.

Use a monotonic queue (a deque) when you have:

A maximum or minimum of every sliding window, for example the highest price in each 7-day window.
A moving window where old items must leave from the front and useless items from the back.

Use something else when:

You need the k-th largest or a stream's median: use a heap.
The window needs a sum or an average: use a sliding window with a running total.
The data changes and you need range maximums: use a segment tree or a sparse table.

There is nothing to import. A monotonic stack is an ordinary stack (a list, ArrayDeque or Vec) with one rule for pushing, and the queue is an ordinary deque.

How a monotonic stack works

A monotonic stack is a stack whose items are always in sorted order, from bottom to top: always decreasing or always increasing. It keeps the order by popping any item that would break it before pushing the new one.

Before pushing a new item, pop every item that breaks the order. Each popped item has just found its answer.

For "next greater element" keep the stack decreasing. A number waits on the stack until a bigger number arrives. When one does, every smaller number on top is popped and gets that bigger number as its answer. The new number is then pushed.

Why it is fast: each item is pushed once and popped at most once. The while loop inside the for loop looks like O(n²), but across the whole run it does at most n pops, so the total is O(n).

The same trick has two relatives:

Monotonic queue. A deque of indexes kept in decreasing value order. The front is the maximum of the current window. A new big number removes smaller numbers from the back, because they can never be the maximum again. Numbers that slide out of the window are removed from the front.
Largest rectangle. A stack of bars in increasing height. When a shorter bar arrives, each taller bar is popped and its rectangle is measured, because it cannot grow to the right any further.

Try it

Pick one of the three problems, then press Run and step through. The line under the rows shows the stack or queue.

Monotonic stack and queue

Step 1 of 9 · Press Space to play, arrow keys to step

Examples:

Numbers (teal = waiting on the stack)

Next greater element to the right

Stack, bottom to top: empty

Find the next greater number to the right of each number. The stack holds numbers still waiting for a bigger one, and it stays in decreasing order.

pushes:: 0
pops:: 0
brute force checks:: 10

Every number is pushed once and popped at most once, so pushes and pops never exceed the number of items, however the data looks.

Speed

Things to try:

Next greater element, "Short list": for 4 5 2 10 8 the stack finds 5 10 10 none none with 5 pushes and 3 pops. Checking every pair would take 10 comparisons, and the gap widens fast as the list grows.
Sliding window maximum, "Classic": for 1 3 -1 -3 5 3 6 7 with k = 3 the maximums are 3 3 5 5 6 7. Watch the queue drop small numbers from the back when a bigger one arrives.
Largest rectangle, "Six bars": for 2 1 5 6 2 3 the stack pops bars 6 and 5 when it reaches the shorter bar 2, and finds a rectangle of area 10 (height 5, width 2).

Monotonic stack and queue operations

Next greater element.

Keep a stack of indexes whose values decrease from bottom to top.
For each number, while the top's value is smaller, pop it and give it the current number as its answer.
Push the current index. Numbers left at the end have no answer.

Sliding window maximum.

Keep a deque of indexes with decreasing values.
For each new number, pop from the back while the back's value is smaller than or equal to it. Push the new index.
If the front's index has left the window, pop it from the front.
Once the first window is full, the front is the answer for each window.

Largest rectangle in a histogram.

Keep a stack of bar indexes with increasing heights.
When a bar is shorter than the top, pop the top. Its width runs from just after the new top to the current index.
Compute height × width and keep the largest. Add a bar of height 0 at the end to flush the stack.

Interview fact. Store indexes, not values, on the stack. You need the index to compute distances, widths and whether a number has left the window.

Monotonic stack and queue time complexity

Problem	Time	Extra memory
Next greater or smaller element	O(n)	O(n)
Sliding window maximum	O(n)	O(k)
Largest rectangle in a histogram	O(n)	O(n)

Each item enters and leaves the stack or queue once, so the pops can never outnumber the pushes. The worst case for memory is a stack that never pops, such as a list that always falls.

Monotonic stack vs other approaches

n is the number of items and k is the window size.

What you need	Monotonic stack or queue	Check every pair	Heap	Segment tree
Next greater element for every item	O(n)	O(n²)	Not helpful	Not needed
Maximum of every window of `k`	O(n)	O(n times k)	O(n log n)	O(n log n)
Largest rectangle in a histogram	O(n)	O(n²)	Not helpful	O(n log n)
Maximum of any range, data changes	Not suitable	O(n) per query	Not suitable	O(log n) per query

The bold cells show where each wins. The monotonic structures win on one-pass questions over a fixed array. They lose when the data changes or the ranges are arbitrary.

How to explain a monotonic stack in an interview

Say what order the stack keeps and why: "decreasing, so a bigger number can resolve everything smaller on top".
Say why it is O(n) even with a while inside a for: "each index is pushed once and popped at most once".
Mention you store indexes, so you can compute distances and widths.
For sliding windows, explain the two ends: "smaller numbers leave from the back, expired numbers leave from the front".
State both costs: O(n) time, and O(n) memory for a stack or O(k) for the queue.

Where you meet monotonic stacks and queues in real systems

Whenever software asks "what is the nearest bigger value?" or "what is the maximum over the last few readings?" while data streams past, a monotonic stack or queue is a good fit. Three examples are drawn out below, the first with code you can run, then more.

Example 1: Days until a warmer day

A weather app shows, for each day, how many days you must wait until it is warmer. Comparing each day with every later day takes O(n²). A monotonic stack keeps the days still waiting for a warmer one, and each new day settles every colder day on top of the stack. The same file also has the window-maximum routine used for "highest reading in the last k readings". Open the example below to see the picture and the code.

Code: days until warmer, and the maximum of every windowTime O(n)Memory O(n) for the stack, O(k) for the queue

On day 0 the temperature is 73 and the next warmer day is day 1, so the wait is 1. On day 2 (75) the next warmer day is day 6 (76), so the wait is 4. The last two days never see a warmer day, so their answer is 0.

Run on the temperatures 73 74 75 71 69 72 76 73, all five versions print the waits 1 1 4 2 1 1 0 0. Run on 1 3 -1 -3 5 3 6 7 with k = 3, all five print the window maximums 3 3 5 5 6 7. The C++ code builds with -std=c++17.

from collections import deque


def days_until_warmer(temps):
    """For each day, how many days until a warmer one? 0 if there is none.

    A monotonic stack holds the days still waiting for a warmer day. Their
    temperatures only go down from the bottom to the top. When today is warmer than
    the day on top, that day has found its answer, so it is popped. Each day is
    pushed once and popped at most once.

    Time:   O(n). Every day is pushed once and popped at most once.
    Memory: O(n). In the worst case (falling temperatures) every day waits on the stack.
    """
    answer = [0] * len(temps)
    waiting = []                                     # indexes of days, temperatures decreasing
    for today, temp in enumerate(temps):
        while waiting and temps[waiting[-1]] < temp: # today is warmer than the day on top
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    return answer


def window_maximums(nums, k):
    """The maximum of every window of k numbers, left to right.

    A monotonic queue (deque) holds the indexes of candidates for the maximum. Their
    values go down from front to back. The front is always the maximum of the window.
    Smaller numbers behind a bigger new number can never be the maximum again, so they
    are dropped from the back. Numbers that slid out of the window are dropped from the front.

    Time:   O(n). Every index enters and leaves the deque at most once.
    Memory: O(k). The deque never holds more than k indexes.
    """
    result = []
    candidates = deque()                             # indexes, values decreasing
    for i, x in enumerate(nums):
        while candidates and nums[candidates[-1]] <= x:
            candidates.pop()                         # smaller and older: never the maximum again
        candidates.append(i)
        if candidates[0] <= i - k:                   # the front slid out of the window
            candidates.popleft()
        if i >= k - 1:
            result.append(nums[candidates[0]])       # the front is the window's maximum
    return result

Example 2: The highest price in the last few days

A trading dashboard shows the highest price in the last 3 trading days, updated as each new price arrives. Re-scanning the last 3 prices every time costs k comparisons per price. A monotonic queue keeps only the prices that could still be the highest, so each price is handled once.

With prices 1, 3, -1, -3, 5, 3, 6 and 7, the first window (1, 3, -1) has a highest price of 3. The window then slides one day at a time, giving 3, 5, 5, 6 and 7.

Example 3: The largest rectangle of free space

Layout and image tools sometimes need the largest empty rectangle in a picture. Treat each row of the picture as a histogram where each bar is how many empty cells are stacked above that column, then find the largest rectangle under the bars. A monotonic stack does it row by row in linear time.

The bars have heights 2, 1, 5, 6, 2 and 3. The two tallest neighbouring bars, 5 and 6, give a rectangle of height 5 and width 2, an area of 10, which is the largest possible.

More real-world scenarios

4. Stock span

A trading screen shows, for each day, how many days in a row the price was at or below today's price. A monotonic stack of earlier prices finds that count in one pass.

5. Skyline and visibility

For a row of buildings, the next taller building to the right decides which buildings are in its shadow or hidden from view. A monotonic stack answers it for every building at once.

6. Expression parsing

Parsers that turn a + b * c into a tree keep a stack of operators. Before pushing a new operator they pop the ones with higher or equal precedence, so the stack stays ordered by precedence.

7. Rolling maximums in monitoring

A monitoring system shows the highest latency in the last 60 seconds. It keeps a monotonic queue of the readings that could still be the highest, so each new reading costs constant time on average.

8. Indentation in languages

Python's tokenizer keeps a stack of indentation levels, in increasing order. A line indented less than the top pops levels, which is how the end of a block is found.

9. Charts and sparklines

Candlestick and sparkline charts mark the highest and lowest value over a rolling window. Streaming charts update those marks with a monotonic queue instead of rescanning the window on every tick.

10. Coding interviews

Daily temperatures, stock span, next greater element and the largest rectangle in a histogram are common interview problems, and all use the same stack idea.

Language standard libraries

You need an ordinary stack for the next-greater problems and a deque for sliding windows. Every language has one, except where noted.

Language	Structure or class	What it is under the hood	Notes
Java	`ArrayDeque`	Resizable circular array	Use it as both the stack (`push`, `pop`) and the deque (`pollFirst`, `pollLast`). Prefer it over the old `Stack` class.
C++	`std::stack`, `std::deque`	Adapter over a deque, and a double-ended queue	`std::vector` also works as a stack with `push_back` and `pop_back`.
C#	`Stack<T>`, `LinkedList<T>`	Array-backed stack, doubly linked list	There is no built-in deque. A `LinkedList<T>` gives O(1) at both ends.
Rust	`Vec`, `VecDeque`	Growable array, ring buffer	A `Vec` is the stack. `VecDeque` is the deque.
Python	`list`, `collections.deque`	Dynamic array, blocks of items	A `list` is the stack. Use `deque` for the queue, because `list.pop(0)` is O(n).
Go	Slices, `container/list`	Slice over an array, doubly linked list	There is no stack or deque type. A slice with `append` and re-slicing does the job.
JavaScript	`Array`	Engine-defined array	`push` and `pop` are the stack. `shift` can be slow on very large arrays, so use two indexes for a long queue.
Kotlin	`ArrayDeque`	Resizable circular array	`kotlin.collections.ArrayDeque` works as stack and deque.

The pattern: the structure is an everyday stack or deque. What makes it monotonic is the loop that pops items before pushing, and you always write that part yourself.

The takeaway

Whenever a system needs the nearest bigger or smaller value, or the maximum over a moving window, look for a monotonic stack or queue. When it needs the k-th largest or a median, it usually uses a heap instead, and when the data changes, a segment tree.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
For each number in an array, find the next greater number to its right, or -1 if there is none. Do it in O(n).
medium
2.
Given daily temperatures, return for each day how many days you must wait for a warmer one (0 if never).
medium
3.
Return the maximum of every window of k consecutive numbers in an array, in O(n).
hard
4.
Given the heights of bars in a histogram, find the area of the largest rectangle that fits inside it.
hard

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Prefix Sums and Difference Arrays

Sorting and Binary Search

Topics:Monotonic stackMonotonic queueNext greater elementSliding window maximumLargest rectangle in histogramDeque