被大厂面试官问烂的算法图解：你还不明白如何找出栈中的最小值？我们今天的面试题是这样的...题目定义

我们今天的面试题是这样的...
题目定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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 地址：leetcode-cn.com/problems/ba…
思考首先来说这道题目本身很好理解，它的实现难点在于以下两个方面：

当我们进行 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执行出栈操作，如下图所示： [图片上传中...(image-f68dcf-1602769401330-6)]
元素 1 出栈，判断当前元素就是栈的最小值，因此将栈顶元素 3 设置为最小值，并移除元素 3 ，如下图所示：

文章插图
操作步骤6继续出栈，如下图所示：

文章插图
因为元素 5 不是当前最小值，因此直接出栈。
操作步骤7继续出栈，如下图所示：

文章插图