Simple python DP solution


  • 0
    F
    class MinStack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=[]
        self.minDP=[999999999999]
    
    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.stack+=[x]
        self.minDP.append(min(self.minDP[-1],x))
    
    def pop(self):
        """
        :rtype: nothing
        """
        if self.stack != []:
            self.stack.pop()
        if len(self.minDP)>1:
            self.minDP.pop()
    
    def top(self):
        """
        :rtype: int
        """
        if self.stack != []:
            return self.stack[-1]
        
    def getMin(self):
        """
        :rtype: int
        """
        return self.minDP[-1]

  • 0
    D

    self.minDP=[999999999999]

    can be replaced with self.minDP=[float('Inf')]


  • 0
    F

    Well, I did not know this though, I used sys.maxint very often, since python's max integer depends on the systems, but in this case, this number is enough. Thanks BTW.


  • 0
    A

    Optimized a lil more....

    class MinStack(object):

    def __init__(self):
        self.stack=[]
        self.stack_min=[float('Inf')]
        
    def push(self, x):
        self.stack.append(x)
        self.stack_min.append(min(self.stack_min[-1],x))
        
    def pop(self):
        if self.stack:
            self.stack.pop()
            self.stack_min.pop()
            
    def top(self):
        return self.stack[-1]
        
    def getMin(self):
        return self.stack_min[-1]

Log in to reply
 

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