题目
- 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1：
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
法一、辅助栈
- 在每个元素 a 入栈时把当前栈的最小值 m 用一个辅助栈存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
class MinStack:
def __init__(self):
self.stack = [] #初始化栈
self.min_stack = [math.inf] #初始化辅助栈
def push(self, x: int) -> None:
self.stack.append(x) #加入栈
self.min_stack.append(min(x, self.min_stack[-1])) #取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
def pop(self) -> None:
self.stack.pop() #出栈
self.min_stack.pop() #辅助栈的栈顶元素也一并弹出
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int: #在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
return self.min_stack[-1]
法二、一个栈同时保存当前值和栈内最小值
- 可以用一个栈，这个栈同时保存的是每个数字 x 进栈的时候的值 x与 插入该值后的栈内最小值。即每次新元素 x 入栈的时候保存一个元组：（当前值 x，栈内最小值）。
这个元组是一个整体，同时进栈和出栈。即栈顶同时有值和栈内最小值，top()函数是获取栈顶的当前值，即栈顶元组的第一个值； getMin() 函数是获取栈内最小值，即栈顶元组的第二个值；pop() 函数时删除栈顶的元组。
每次新元素入栈时，要求新的栈内最小值：比较当前新插入元素 x 和 当前栈内最小值（即栈顶元组的第二个值）的大小。
class MinStack(object):
def __init__(self):
self.stack = [] #初始化栈
def push(self, x):
"""
:type x: int
:rtype: void
"""
if not self.stack: #栈为空
self.stack.append((x, x))
else: #栈不空
self.stack.append((x, min(x, self.stack[-1][1]))) #保存元组 (x, min(此前栈内最小值， x)))
def pop(self):
self.stack.pop()#删除栈顶的元组
def top(self): #获取栈顶的当前值，即栈顶元组的第一个值
return self.stack[-1][0]
def getMin(self): #获取栈内最小值，即栈顶元组的第二个值
return self.stack[-1][1]