Monotonic Stack

A monotonic stack holds the positions of an array that are still waiting for an answer, kept in sorted order of value, so that each new value answers every waiting position it beats and the whole array is answered in one pass. It matters because finding the nearest larger or smaller value for every position by scanning costs O(n²), and the stack does it in O(n), since every position is pushed once and popped at most once. The topic finds the next greater value for every position, counts the days until a river rises above each day's level, and gives the template in Python, Java and TypeScript. It adapts the template to a circular array and to how far back each building's view reaches along a street, shows why the stack must hold indices when the answer is a distance, and ends with an exercise on waiting for a cheaper fare.