A STACK ONLY EVER ADDS OR REMOVES AT THE TOP. SO WHEN YOU PUSH A VALUE, ALSO REMEMBER THE SMALLEST VALUE IN THE STACK AT THAT MOMENT, AND STORE THE PAIR. THE TOP PAIR ALWAYS CARRIES THE CURRENT MIN, AND POPPING IT UNCOVERS THE PREVIOUS MIN FOR FREE.

THE OPS TAPE RUNS LEFT TO RIGHT, THE OP POINTER ON THE CURRENT CALL. THE STACK SHELF HOLDS ONE PILL PER LEVEL, EACH READING THE VALUE AND THE MIN STORED WITH IT. PUSH SPRINGS A PILL IN, POP LIFTS ONE OUT, AND A GREEN TOP PILL IS THE PAIR THAT TOP OR GETMIN READS.

1class MinStack:2    def __init__(self):3        self.stack = []  # (val, min) pairs4    def push(self, val):5        if not self.stack:6            cur_min = val7        else:8            cur_min = min(val, self.stack[-1][1])9        self.stack.append((val, cur_min))10    def pop(self):11        self.stack.pop()12    def top(self):13        return self.stack[-1][0]14    def getMin(self):15        return self.stack[-1][1]