My Python solution


  • 73
    C
    class MinStack:
    
    def __init__(self):
        self.q = []
    
    # @param x, an integer
    # @return an integer
    def push(self, x):
        curMin = self.getMin()
        if curMin == None or x < curMin:
            curMin = x
        self.q.append((x, curMin));
    
    # @return nothing
    def pop(self):
        self.q.pop()
    
    
    # @return an integer
    def top(self):
        if len(self.q) == 0:
            return None
        else:
            return self.q[len(self.q) - 1][0]
    
    
    # @return an integer
    def getMin(self):
        if len(self.q) == 0:
            return None
        else:
            return self.q[len(self.q) - 1][1]

  • 5
    G

    your idea of using curMin = self.getMin() to initialize curMin in first place is so smart. Thank u


  • 3
    C

    brilliant! I've almost forget tuple until I found this solution!


  • 21
    E

    You can just use self.q[-1] instead of self.q[len(self.q)-1] to get the last element.


  • 0
    E

    Your idea is great. But I don't know why I have a run time error...


  • 0
    A

    Brilliant!!Using current min to restore the Min value at that point,and set&get min become an o(1) function! Thanks very much!


  • 0
    W

    wow, very nice


  • 0
    A

    PEP8 - "Comparisons to singletons like None should always be done with is or is not , never the equality operators."

    I would suggest replacing "currMin == None" with "currMiin is None"


  • 14

    Here's my updated version:

    class MinStack(object):
    
        def __init__(self):
            self.stack = []
            
        def push(self, x):
            self.stack.append((x, min(self.getMin(), x))) 
               
        def pop(self):
            self.stack.pop()
    
        def top(self):
            if self.stack:
                return self.stack[-1][0]
            
        def getMin(self):
            if self.stack:
                return self.stack[-1][1]
            return sys.maxint            
    
    

  • 0
    P

    This is such a beautiful solution! Thank you!!


  • 0
    M

    The use of a tuple to maintain the min and the latest value is ridiculously smart...


  • 0
    S

    @Evaxue me too,have you solved the problem?


  • 0
    Z

    '''class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.q = []
        
    
    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.q.insert(0,x)
        
    
    def pop(self):
        """
        :rtype: void
        """
        try:
            self.q = self.q[1:]
        except:
            return "null"
    
    def top(self):
        """
        :rtype: int
        """
        if self.q:
            return self.q[0]
    
    def getMin(self):
        """
        :rtype: int
        """
        try:
            return min(self.q)
        except:
            return null
    

    '''
    I wrote my code like this, while it cannot be accepted because of time limited. Will it be fine?


  • 0
    G

    @zhipinggao I think your problem is getMin(self) because every time calling it will also call the function min(). This complexity is too high.


  • 0
    S

    but for this question..should we only use .pop() to pop...
    OR use sth like:

    def pop(self):
            if self.isEmpty():
                raise EmptyStackError()
            item = self.data[len(self.data) -1]
            del self.data[len(self.data) -1]
            return item
    

  • 0

    Anyone who can tell me, why do we need to make use of tuple here? Why can`t we make use of 1-dimensional list directly ?


  • 1
    S

    @Ivan_Ouyang Hey Ivan, if you try the way that you came up with, you will see TLE (Time Limit Exceeded) result.


  • 0
    L

    @charles8135 I was thinking how to keep track of the second min. Your solution of storing the current min is so smart!


  • 0
    L

    @Ivan_Ouyang It will take up too much time. Since every time you will need to re-search the rest of the stack to find the min again.


  • 0
    L

    @Seasean del in Python takes O(n) time while pop in Python only takes O(1).


Log in to reply
 

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