Python O(n) with 2 stacks


  • 0
    L

    Hardest part of this question is figuring out an efficient was to pop max. I originally was trying to do something similar to LFU cache with double linked lists, but couldn't figure out how to save the sequential maxes after popping the max. So right now I take the brute force approach of popping everything out from both stacks until we reach the max, and add the elements that were previously popped, back in.

    class MaxStack(object):
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.stk=[]
            self.maxstk=[]
    
        def push(self, x):
            """
            :type x: int
            :rtype: void
            """
            self.stk.append(x)
            if not self.maxstk:
                self.maxstk.append(x)
            else:
                self.maxstk.append(max(x,self.maxstk[-1]))
    
        def pop(self):
            """
            :rtype: int
            """
            self.maxstk.pop()
            return self.stk.pop()
        def top(self):
            """
            :rtype: int
            """
            return self.stk[-1]
    
        def peekMax(self):
            """
            :rtype: int
            """
            return self.maxstk[-1]
    
        def popMax(self):
            """
            :rtype: int
            """
            n=self.maxstk.pop()
            i=len(self.stk)-1
            tmp=[]
            while n!=self.stk[-1]:
                tmp.append(self.pop())
            ret=self.stk.pop()
            for i in xrange(len(tmp)-1,-1,-1):
                self.push(tmp[i])
            return ret

Log in to reply
 

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