Monotonic Stack

A stack that removes useless candidates in time

A monotonic stack is a regular stack whose elements are kept in increasing or decreasing order. Before adding a new value, we remove elements from the top when they can no longer be useful for the answer. The stack therefore stores only relevant candidates instead of the entire history.

Example: next greater element

For each array element, let us find the first value to its right that is greater than it. The stack will store indexes of elements whose answer has not been found yet. When a larger value arrives, it immediately resolves the waiting elements that are suitable at the top.

static int[] nextGreater(int[] numbers) {
    int[] result = new int[numbers.length];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < numbers.length; i++) {
        while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
            int index = stack.pop();
            result[index] = numbers[i];
        }
        stack.push(i);
    }

    return result;
}

Why this is O(n) despite the nested while loop

Each index enters the stack exactly once and is removed at most once. The total number of stack operations is therefore linear, so the whole algorithm runs in O(n) time and uses O(n) additional memory.

The key question for this technique is: when does a candidate become useless forever? If that can be decided by a local comparison with the new element, a monotonic stack often removes the need for repeated array scans.