155. Min Stack

'''
• We need a way to always know the minimum so far without scanning the whole stack, since that would be O(n).

• While pushing, store not only the value but also the minimum up to that point, so every stack level “remembers” the smallest value below it.

• Then pop, top, and getMin become simple lookups from the top element, all in O(1) time.
'''

class MinStack:
    def __init__(self):
        self.st = []

    def push(self, val: int) -> None:
        if not self.st:
            self.st.append((val, val))
        else:
            self.st.append((val, min(val, self.st[-1][1])))

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]