Python O(n) with 2 stacks

• 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):
"""
"""
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``````

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