前面我们学习了很多关于栈的知识，比如《动图演示：手撸堆栈的两种实现方法！》和《JDK 竟然是这样实现栈的？》，那么接下来我们再来刷一些关于栈的经典面试题以巩固学过的知识。
我们今天的面试题是这样的...
题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
LeetCode 地址：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
思考
首先来说这道题目本身很好理解，它的实现难点在于以下两个方面：
- 当我们进行 pop（移除栈顶元素）操作时如果删除的是当前最小值，那么我们如何寻找下一个最小值？
- 要保证调用 min、push 及 pop 的时间复杂度都是 O(1)。
也就是说，在我们执行了 pop 时如果移除的栈中最小的值，那么如何寻找栈中的下一个最小元素？并且要保证操作的时间复杂度为 O(1)。这个时间复杂度制约了我们在移除了最小值之后不能通过遍历查找下一个最小值，所以这就成为了这道题的难点。
比如当我们移除以下栈顶元素值：
因为最小值就是 1，因此在移除之后最小值也被移除了，如下图所示：
那么接下来，让我们一起思考 3 分钟，想一想应该如何处理这个问题~
解题思路
其实我们可以在每次入栈时，判断当前元素是否小于最小值，如果小于则将原最小值和最新的最小值相继入栈，这样在调用 pop 时即使移除的是最小值，我们也能通过获取下一个元素得到一个新的最小值，执行流程如下所示。
操作步骤1
入栈第一个元素，因为是第一个元素，因此最小值就是此元素的值。
操作步骤2
入栈第二个元素，如下图所示：
因为入栈的元素 3 比 8 小，所以先将栈中的原最小值 8 存入栈中，再将 3 入栈。
操作步骤3
入栈第三个元素，如下图所示：
因为入栈元素 5 大于 3，因此栈中的最小值不变，直接将元素 5 入栈。
操作步骤4
继续入栈，如下图所示：
入栈元素 1 小于于 3，因此先将原最小值 3 入栈，再将 1 入栈，栈中的最小值更改为 1。
操作步骤5
执行出栈操作，如下图所示：
元素 1 出栈，判断当前元素就是栈的最小值，因此将栈顶元素 3 设置为最小值，并移除元素 3，如下图所示：
操作步骤6
继续出栈，如下图所示：
因为元素 5 不是当前最小值，因此直接出栈。
操作步骤7
继续出栈，如下图所示：
因为出栈元素 3 为最小值，因此继续将最小值设置为栈顶元素 8，并将栈顶元素出栈，如下图所示：
这样就剩下最后一个元素了，最后一个元素出栈之后就成空栈了，整个流程就执行完了。
