Any O(1) sol getMin() after pop()?


  • 0
    R

    It's annoying..

    Sorry for being picky. But I think it seems impossible to retain the trace of getMin() after several pop() in time of O(1).

    Please enlighten me if you get any idea

    First Thought

    Initial:
    s = [3, 2, 1, -1]
    getMin()  // -1
    pop()     // s = [3, 2, 1]
    getMin()  // should be 1 at index 2
    

    But how can we find this index in linear time?
    We can introduce another pointer preMin, but what if there is another pop()?

    Continue:
    pop()    // s = [3, 2]
    getMin() // should be 2 at index 1
    

    if seems to get chained up by the number of calling of pop()


    Another Thought

    We might have another sorted list/array/vector to keep track of the elements have been pushed into MinStack. But I believe it would introduce extra cost to push() method and boost the time complexity to O(lg(n))(e,g, binary search).


  • 1
    A

    Maintaining an extra list to obtain Min from the stack will cost you, but not as much as calling the min function on the whole stack. Here's my code, check it out. stack_min will always have min element at the end, at any given point of time. Complexity is O(1) here.

    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.