Problem. Design a stack with push(x), pop(), top() and get_min(), all in O(1) time. get_min()
returns the smallest element currently in the stack.
push(-2), push(0), push(-3)
get_min() → -3
pop()
top() → 0
get_min() → -2
The hard part is pop(): when the minimum leaves, the previous minimum must be available instantly, without
looking through the stack.
ML context. A stack with "best so far" appears whenever you can roll back: a search over model configs where you try a change, undo it if it doesn't help, and always want the best validation loss among the current path; an undo history in a notebook tool; backtracking search (module 08). And two min-stacks make a min-queue, which gives the rolling minimum of a loss curve for plateau detection (Change B).