设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
class MinStack(object):
def __init__(self):
self.stack = [] # 存放所有元素
self.minStack = []
def push(self, x):
self.stack.append(x)
if not self.minStack or self.minStack[-1] >= x:
self.minStack.append(x)
def pop(self): # 移除栈顶元素时,判断是否移除栈中最小值
if self.minStack[-1] == self.stack[-1]:
del self.minStack[-1]
self.stack.pop()
def top(self): #获取栈顶元素
return self.stack[-1]
def getMin(self): #获取栈中的最小值
return self.minStack[-1]
def all(self): #列表栈中所有的元素
return self.stack[:]
我们每次入栈的时候,保存的不再是真正的数字,而是它与当前最小值的差(当前元素没有入栈的时候的最小值)。 这样我们pop和top的时候拿到栈顶元素再加上上一个最小值即可。 另外我们在push和pop的时候去更新min,这样getMin的时候就简单了,直接返回min。