My AC code:
class MinStack: # @param x, an integer def __init__(self): # the stack it self self.A =  self.minS= # @return an integer def push(self, x): n=len(self.A) if n==0: self.minS.append(x) else: lastmin=self.minS[-1] if x<=lastmin: self.minS.append(x) self.A.append(x) # @return nothing def pop(self): if len(self.A)>0 and self.A.pop()==self.minS[-1]: self.minS.pop() # @return an integer def top(self): return self.A[-1] # @return an integer def getMin(self): return self.minS[-1]
However, at my first try, I use tuples in list [(element, min_value_sofar)] and got MLE. Can anyone explain the reason? I thought that the memory is still O(n).
My complete solution blog: http://randombet.blogspot.com/2014/09/151-accepted-python-solutions-for_19.html
I'm not sure the reason yet but you need to check if the list is empty before you return list[-1] or may lead to an error
Which code are you talking about? I posted my accepted code and asked a question why I can't implement the same algorithm using tuple without MLE.
I think when you use tuple, the space used is 2 * n, because every pushed tuple has 2 items. But use 2 stacks, only when pushed number is less than the current min value, it will be pushed in minStack. So the space used is less than 2n.
However, I used a one stack solution, which is rewritten from a Java solution that you can find it in another post. I think it will use less memory, but it got MLE error. Who can explain this to me?
I guess the pointer of tuple needs space, so if you use any pointer, it's easy to get MLE.
There is a clever in the pop method, thanks for sharing this solution.
In this solution, size of minS might be smaller than size of A. So the average space complexity is no more than O(2 * n). Although it's the same as O(n) in big Oh theory, but I think it's treated differently here. BTW thanks for your blog. It's really inspiring.
Hi, i tried you solution but without declaration of
lastmin in push method. And i get a MLE result. Why is it? Is it possible your solution is almost at the boundary of memory limit?
It seems that your code not only have the MLE problem, but also can't work well without memory limited.
For push(), every time before you push a x into A, you compare x with the top value in minS, but if x is smaller than the value which is not on the top of minS, it will confuse the order of minS.
The order of minS is exactly the way I want it to be. minS stores the minimal value when it is stored on the top.
Thanks for sharing this. Although it works correctly in my local copy of Python, the Online Judge does not seem to agree. In the test case "push(-1),top,getMin", it gives a very strange output: [-1, -3]. I wonder if anyone knows why.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.