Monotonic Stack

Maintain a stack in strictly increasing or decreasing order; each push pops all violating elements which receive their answer at that moment.

Maintain a stack in strictly increasing or decreasing order; each push pops all violating elements which receive their answer at that moment.

The stack holds indices of elements whose answer is not yet resolved; the ordering invariant ensures a violating push is simultaneously the answer for all elements it pops.

Each element is pushed and popped at most once — a violating push answers all popped elements simultaneously, giving O(n) total work.

Storing indices (not values) lets the algorithm compute distances, spans, or widths at pop time.