Monotonic stack

O(n)

Keep the stack's values strictly increasing (or decreasing) from bottom to top by popping every element the new one beats before pushing it; each pop just found its next-greater (or next-smaller) element.

Signals

next greater / next smaller elementdaily temperatures until it gets warmerlargest rectangle in a histogramtrap rainwater between barsspan/streak that ends at the first bigger or smaller value

Template

function nextGreater(nums) {
    const result = new Array(nums.length).fill(-1);
    const stack = [];
    for (let i = 0; i < nums.length; i++) {
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

Looks similar, isn't

Stack: A plain stack matches pairs in the order they appear (open with its own close). Reach for a monotonic stack specifically when the question is next/previous greater or smaller element, which needs the stack kept sorted, not just balanced.

n up to 1e5 elements -> O(n): each element is pushed once and popped at most once, even though it looks like a nested loop.

Learn this pattern