Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Example 1:
Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
Constraints:
pop
, top
and getMin
operations will always be called on non-empty stacks.Source
# Your MinStack object will be instantiated and called as such:
obj = MinStack()
obj.push(x)
obj.pop()
param_3 = obj.top()
param_4 = obj.getMin()
class MinStack:
def __init__(self):
"""initialize your data structure here."""
self.stack = []
def push(self, n):
"""return none
TRICK: each node in the stack has a minimum value"""
if len(self.stack) == 0:
self.stack.append((n, n))
else:
self.stack.append((n, min(n, self.stack[-1][1])))
def pop(self):
"""return none."""
return self.stack.pop()[0] #return element
def top(self):
"""return int."""
return self.stack[-1][0] #return element
def getMin(self):
"""return int."""
return self.stack[-1][1] #return min value associated with element