Intuition

Use a stack to keep current element and current_min

Approach

Use a stack to keep current element and current_min

Complexity

  • Time complexity: O(1)

  • Space complexity: O(n)

Code

class MinStack(object):
    def __init__(self):
        self.stack = []
        self.min = float('inf')

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """

        self.min = min(val, self.min)
        item = {
            "val": val,
            "min": self.min
        }
        self.stack.append(item)
        

    def pop(self):
        """
        :rtype: None
        """

        self.stack.pop()
        if len(self.stack) > 0:
            self.min = self.stack[-1]['min']
        else:
            self.min = float('inf')
        

    def top(self):
        """
        :rtype: int
        """

        return self.stack[-1]["val"]

    def getMin(self):
        """
        :rtype: int
        """
        return self.min