Monotonic Stack/Deque Intro

If you'd prefer a video:

A monotonic stack keeps its values in sorted order as you push elements. The order can be increasing or decreasing, depending on the problem.

A decreasing monotonic stack is the most common version. Before pushing a new value x, we pop from the top while the top is smaller than or equal to x. After those pops, pushing x keeps the stack decreasing from bottom to top.

This push rule is the whole idea. A monotonic deque uses the same rule, but a deque also lets you remove old elements from the front, which is useful for sliding window problems.

The diagram below shows a decreasing monotonic stack.

Example implementation

This implementation maintains a decreasing monotonic stack.

1def mono_stack(insert_entries):
2    stack = []
3    for entry in insert_entries:
4        # Pop smaller (or equal) values so stack stays decreasing.
5        while stack and stack[-1] <= entry:
6            stack.pop()
7            # Do something with the popped item here
8        stack.append(entry)
9

1public static void monoStack(List<Integer> insertEntries) {
2    ArrayList<Integer> stack = new ArrayList<>();
3    for (int entry : insertEntries) {
4        // Pop smaller (or equal) values so stack stays decreasing.
5        while (!stack.isEmpty() && stack.get(stack.size() - 1) <= entry) {
6            stack.remove(stack.size() - 1);
7            // Do something with the popped item here
8        }
9        stack.add(entry);
10    }
11}
12

1function monoStack(insertEntries) {
2    const stack = [];
3    for (let entry of insertEntries) {
4        // Pop smaller (or equal) values so stack stays decreasing.
5        while (stack.length > 0 && stack[stack.length - 1] <= entry) {
6            stack.pop();
7            // Do something with the popped item here
8        }
9        stack.push(entry);
10    }
11}
12

1void mono_stack(std::vector<int> insert_entries) {
2    std::vector<int> stack;
3    for (int entry : insert_entries) {
4        // Pop smaller (or equal) values so stack stays decreasing.
5        while (!stack.empty() && stack.back() <= entry) {
6            // Do something with the top item in stack here
7            stack.pop_back();
8        }
9        stack.push_back(entry);
10    }
11}
12

1function monoStack(insertEntries: number[]): void {
2    const stack: number[] = [];
3    for (const entry of insertEntries) {
4        // Pop smaller (or equal) values so stack stays decreasing.
5        while (stack.length > 0 && stack[stack.length - 1] <= entry) {
6            stack.pop();
7            // Do something with the popped item here
8        }
9        stack.push(entry);
10    }
11}
12

In interview problems, the stack usually stores indices instead of values. You can read the value from the original array when needed, and the index gives you distance information such as "how many steps away is the next greater element."

For an array nums, if index j pops when you process index i, then i is the first index to the right that satisfies the stack condition for j. In a next-greater-element problem, that means nums[i] is the next greater value for nums[j].

Applications of monotonic stack/deque

There are a few interesting properties of a monotonic stack/deque that we can utilize in certain types of questions.

The key benefit is that each element is pushed once and popped at most once, so the total work stays linear. Popping is not wasted work. It tells you that the new element has resolved something for the popped element.

Next Largest or Smallest Element in a List

Suppose nums = [3, 1, 6, 2] and you use a decreasing stack of indices. When you reach 6, you pop 1 and then 3, so 6 is the next greater element for both. This gives the answer while scanning left to right once, for O(n) time.

If the problem also requires a distance limit or a fixed window, use a monotonic deque. The back still enforces monotonic order, and the front removes indices that are now out of range.

For an example, see Daily Temperatures.

Maximum or Minimum Element in a Sliding Window

For window maximum, keep a decreasing deque of indices. The front is always the current maximum. When a new element enters, pop smaller values from the back. When the window moves, remove the front index if it falls outside the window. Each index enters and leaves once, so runtime is O(n).

For an example, see Sliding Window Maximum.