Monotonic Stack and Monotonic Queue

A monotonic stack keeps its elements sorted so the next-greater or next-smaller element falls out in amortized O(n); a monotonic deque does the same for a sliding window maximum. The shared trick is an invariant: before pushing, discard everything that the new element makes useless. Interviews probe these because they turn an obvious O(n^2) scan into a single pass and test whether a candidate can name what the structure never stores.