Monotonic Stacks: Next Greater Element and Beyond

The stack invariant

For each position, “next greater element” asks for the first value to its right that is larger. A naive search starts again from every position and costs O(n²). Instead, scan left to right and store indices whose next greater value is not known yet. Keep their values decreasing from bottom to top. If the current value exceeds the top value, it is the answer for that waiting index; pop and record it. Repeat until the invariant is restored.

Next greater element in one pass

def next_greater(nums):
    answer = [-1] * len(nums)
    waiting = []
    for i, value in enumerate(nums):
        while waiting and nums[waiting[-1]] < value:
            answer[waiting.pop()] = value
        waiting.append(i)
    return answer

Each index is pushed once and popped at most once, so total work is O(n), even though there is a while loop inside the scan. Indices are stored rather than values because the output must be written back to the correct location. Any index still on the stack has no greater value to its right and keeps the default answer.

Increasing, decreasing, and circular variants

Use a decreasing stack when a larger incoming value resolves waiting smaller values. Reverse the comparison for next-smaller queries. For previous-neighbor queries, the same invariant applies but the current element is answered from the stack before it is pushed. Be precise about strict versus non-strict comparisons; duplicates affect whether equal values should remain together.

Monotonic stacks also solve daily temperatures, stock span, and largest rectangle in a histogram. In a histogram, when a shorter bar arrives, it bounds the right edge of taller bars; their widths can then be calculated from the new stack top. For circular arrays, scan two passes but push indices only on the first pass to prevent duplicate work.

• Store indices when answers depend on positions or widths.
• Write the stack's ordering invariant in a comment or explanation.
• Try increasing values, decreasing values, duplicates, and a single element.