Know this before you start: “Monotonic stacks for next greater / smaller”

Monotonic stacks: the next greater element

Keep a stack whose values only decrease. Each new value pops everything smaller: for each popped item, this is its next greater element.

The idea

For “next warmer day” or “next bigger number”, checking every later item is O(n²). A monotonic stack does it in one pass.

Keep indexes of items still waiting for their answer, with values decreasing from bottom to top. When a new value is bigger than the top, the top's answer is the new value: pop and record it, and keep popping while that's true. Then push the new index.

Each index is pushed once and popped once, so it's O(n) overall.

See it step by step

Next greater element in [2, 1, 5, 3]

2 waits. 1 waits on top of it (1 < 2).
5 arrives: beats 1 → its answer is 5; beats 2 → answer 5. 5 waits.
3 waits under nothing bigger. End: 5 and 3 have no answer (−1).
Answers: [5, 5, −1, −1].

In code (Python)

def next_greater(nums):
    answer = [-1] * len(nums)
    stack = []                           # indexes, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            answer[stack.pop()] = x
        stack.append(i)
    return answer

print(next_greater([2, 1, 5, 3]))   # [5, 5, -1, -1]

O(n) time, O(n) space.

When you'll use it

Next greater / smaller, days until warmer, stock spans, largest rectangle in a histogram.

Common mistakes

Storing values instead of indexes when you need distances.
Mixing up < and <= for equal values.