请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
执行push、pop和min操作的时间复杂度必须为O(1)。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
自我解答
push, pop 等都很容易实现O(1), 但怎么能不迭代获取最小值呢？
在每次 push 和 pop 的过程其实就已经访问过每个元素了，可以设置一个变量，
记录最小值，每次 push 检查更新最小值，但 每次 pop 时，需要检查出栈的是不是
最小值，如果是，则需要迭代寻找最小值了，这种情况 pop 的时间复杂就是 O(n)了，
有点不符合题意。但执行效率依然很高
执行用时：60 ms, 在所有 Python3 提交中击败了99.90% 的用户
内存消耗：16.5 MB, 在所有 Python3 提交中击败了53.66%的用户
class MinStack():
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min_x = float("inf")
def push(self, x: int) -> None:
self.stack.append(x)
if self.min_x is None or x < self.min_x:
self.min_x = x
def pop(self) -> None:
if self.stack.pop() == self.min_x:
self.min_x = min(self.stack) if self.stack else None
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_x
题解
题解是用两个栈实现的。
我思考过添加一个队列，把所有元素从大到小排列，这样最后一个就是最小值了。
但是这样在执行效率太低了，不仅每次 push 都需要插入排序，而且每次 pop 时，如果 pop的
是最小值还好处理，但如果 pop 的不是最小值，就还需要从查找删除。 这样显然是行不通的。
那么到底怎么做呢？ 题解使用了非常巧妙的方式：
设置变量： self.stack = [], 用来储存所有数据；
设置变量： self.min_stack = [], 只储存 “<= 栈顶值的数据“ 或 ”当此栈为空时储存任何数据“
我一开始是惯性思维，想着应该对所有数排序。
比如依次将 5,3,4 压入栈中：
如果把所有数都存入 min_stack, 会是这样 [5,4,3], 会想到，3 是最小的，推出 3 后，
最小值理应是第二小的 4， 所以 4 应该也放到 min_stack 中的。但其实是多余的，
因为推出 3 时，4 早就没了。
这也正是 self.min_stack 的巧妙之处，只需要储存 ”更小的数“，之后如果再遇到”第二小的数“，
对于业务：getMin 来说，都是没有意义的。
class MinStack3:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min_stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def top(self) -> int:
return self.stack[-1] if self.stack else None
def pop(self) -> None:
if self.stack:
num = self.stack.pop(-1)
if num == self.min_stack[-1]:
self.min_stack.pop(-1)
def getMin(self) -> int:
return self.min_stack[-1] if self.min_stack else None
虽然没有“自我解答”中的思路好理解，但真正实现了 O(1)