class MinStack:
def __init__(self):
self.q = []
# @param x, an integer
# @return an integer
def push(self, x):
curMin = self.getMin()
if curMin == None or x < curMin:
curMin = x
self.q.append((x, curMin));
# @return nothing
def pop(self):
self.q.pop()
# @return an integer
def top(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q)  1][0]
# @return an integer
def getMin(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q)  1][1]
My Python solution


Here's my updated version:
class MinStack(object): def __init__(self): self.stack = [] def push(self, x): self.stack.append((x, min(self.getMin(), x))) def pop(self): self.stack.pop() def top(self): if self.stack: return self.stack[1][0] def getMin(self): if self.stack: return self.stack[1][1] return sys.maxint


'''class MinStack(object):
def __init__(self): """ initialize your data structure here. """ self.q = [] def push(self, x): """ :type x: int :rtype: void """ self.q.insert(0,x) def pop(self): """ :rtype: void """ try: self.q = self.q[1:] except: return "null" def top(self): """ :rtype: int """ if self.q: return self.q[0] def getMin(self): """ :rtype: int """ try: return min(self.q) except: return null
'''
I wrote my code like this, while it cannot be accepted because of time limited. Will it be fine?

@zhipinggao I think your problem is getMin(self) because every time calling it will also call the function min(). This complexity is too high.

@Ivan_Ouyang Hey Ivan, if you try the way that you came up with, you will see TLE (Time Limit Exceeded) result.

@charles8135 I was thinking how to keep track of the second min. Your solution of storing the current min is so smart!

@Ivan_Ouyang It will take up too much time. Since every time you will need to research the rest of the stack to find the min again.
