My Python solution, the best running time is 208 ms


  • 2
    B
    class MinStack:
        
        def __init__(self):
            self.__stack, self.__minIndex = list(), list()
    
        # @param x, an integer
        # @return an integer
        def push(self, x):
            try:
                if x < self.__stack[self.__minIndex[-1]]:
                    self.__minIndex.append(len(self.__stack))
            except:
                self.__minIndex.append(0)
            self.__stack.append(x)
    
                
        # @return nothing
        def pop(self):
            self.__stack.pop()
            if self.__minIndex[-1] >= len(self.__stack):
                self.__minIndex.pop()
    
    
        # @return an integer
        def top(self):
            return self.__stack[-1]
    
        # @return an integer
        def getMin(self):
            return self.__stack[self.__minIndex[-1]]
    

    The idea is using an extra stack to track the min value. But only keep the index so far. So if a new pushed value is larger than the current min value, nothing will be appended to the min stack.


  • 0
    L

    I am wondering if it will be constant time when you use len()?


  • 0
    B

    Thanks for the comments.The answer is YES. Please refer to this page: https://wiki.python.org/moin/TimeComplexity


  • 0
    L

    Thanks a lot! The resource is pretty good


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.