155

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.main = []
        self.mono = []

    def push(self, x: int) -> None:
        self.main.append(x)
        if not self.mono or x <= self.mono[-1]:
            self.mono.append(x)

    def pop(self) -> None:
        x = self.main.pop()
        if self.mono and x == self.mono[-1]:
            self.mono.pop()
        return x

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

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