Monotonic stacks, deques, and the parsing and next-greater-element families.
4 questions in Data Structures & Algorithms.
Push arrivals onto an inbound stack and serve departures from an outbound one, transferring everything across only when the outbound stack is empty. Transferring on every dequeue instead reverses the order and breaks FIFO, and the empty-only rule is also what makes the amortised cost constant.
Scan left to right holding a stack of indices whose answers are still unknown, kept strictly decreasing by value. Each new element resolves and pops everything smaller than it, then pushes itself. Every index is pushed once and popped at most once, so the scan is O(n) despite the inner loop.
Keep a stack of bar indices with strictly increasing heights. When a bar no taller than the top arrives, pop: the popped bar's rectangle runs from just after the new top to just before the current bar. A height-zero sentinel flushes the stack. Each index is pushed once and popped at most once, so it is O(n).
Keep a deque of indices whose values strictly decrease from front to back. Each step drops the front if it has left the window, pops smaller or equal values from the back, then appends. The front is the window maximum. Each index enters and leaves once, so it is amortised O(n), against O(n log k) for a balanced tree.