Python. Proper O(1) for all operations.


  • 0
    P

    It's proper O(1) for all operations. Not like many solutions using heaps.

    The self.mins list keeps track of the index of all previous minimums for the same position in self.data.
    So even if we pop() the minimum, we fetch the previous one and we never lose it.

    class MinStack(object):                                                                                                                                          
        def __init__(self):
            self.data = []
            self.mins = []
            self.minint = None
            self.minindex = None                                                                                                                                     
        def push(self, x):
            oldmin = None
            if not self.data:
                self.minint = x
                self.minindex = 0
            else:
                if x <= self.minint:
                    self.minint = x
                    oldmin = self.minindex
                    self.minindex = len(self.data)
            self.data.append(x)
            self.mins.append(oldmin)                                                                                                                                 
        def pop(self):
            if self.data:
                if self.mins[-1] is not None:
                    self.minint = self.data[self.mins[-1]]
                    self.minindex = self.mins[-1]                                                                                                                    
                self.mins.pop()
                return self.data.pop()                                                                                                                               
        def top(self):
            if self.data:
                return self.data[-1]                                                                                                                                 
        def getMin(self):
            return self.minint 
    

Log in to reply
 

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