1class MinStack:
2 def __init__(self):
3 self.stack = []
4 self.min_stack = []
5 def push(self, val):
6 self.stack.append(val)
7 val = min(val, self.min_stack[-1] if self.min_stack else val)
8 self.min_stack.append(val)
9 def pop(self):
10 self.stack.pop(); self.min_stack.pop()
11 def top(self): return self.stack[-1]
12 def getMin(self): return self.min_stack[-1]