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

因为出栈元素 3 为最小值，因此继续将最小值设置为栈顶元素 8 ，并将栈顶元素出栈，如下图所示：
文章插图
这样就剩下最后一个元素了，最后一个元素出栈之后就成空栈了，整个流程就执行完了。
实现代码1接下来我们将上面的思路用代码实现一下，我们用数组实现的栈来实现相关的功能，代码如下：
class MinStack {private int[] data; // 栈数据private int maxSize; // 最大长度private int top; // 栈顶指针（下标）private int min; // 最小值// 构造函数public MinStack() {// 设置默认值maxSize = 10000;data = http://kandian.youth.cn/index/new int[maxSize];top = -1;min = Integer.MAX_VALUE;}// 入栈（添加元素）public void push(int x) {if (min>= x) {// 遇到了更小的值，记录原最小值（入栈）data[++top] = min;min = x;}// 当前值入栈data[++top] = x;}// 出栈（移除栈顶元素）public void pop() {if (min == data[top]) {min = data[--top]; // 拿到原最小值，并（将原最小值）出栈}--top; // 出栈}// 查找栈顶元素public int top() {return data[top];}// 查询最小值public int min() {return min;}}上述代码在 LeetCode 的执行结果如下：
文章插图
可以看出性能还是很高的，超越了 99.92% 的用户，内存消耗也不大。它的核心代码在 push 方法内，先将原最小值和最新最小值相继入栈，在 pop 出栈时判断出栈元素是否为最小值，如果是最小值则将当前最小值指向栈顶元素并将栈顶元素出栈，这样就得到了下一个新的最小值了。
实现代码2如果我们不想使用数组的自定义栈来实现，还可以使用 Java 中自带的栈 Stack 来实现此功能，代码如下：
class MinStack {private Stack stack = new Stack<>();private int min = Integer.MAX_VALUE;public MinStack() { }// 入栈（添加元素）public void push(int x) {if (x <= min) {// 遇到了更小的值，记录原最小值（入栈）stack.push(min);min = x;}stack.push(x);}// 出栈（移除栈顶元素）public void pop() {if (stack.pop() == min) {min = stack.pop(); // 取出原最小值}}// 查找栈顶元素public int top() {return stack.peek();}// 查询最小值public int min() {return min;}}上述代码在 LeetCode 的执行结果如下：
文章插图
从结果可以看出，使用 Java 中自带的栈的性能不如自定义数组的栈，但代码还是通过了测试。这种实现方式的优点就是代码比较简单，可以利用了 Java 自身的 API 来完成了最小值的查找。
这种实现代码的方式（使用 Java API），在刷题或者实际面试中如果没有特殊说明是可以直接用的。
总结本文我们通过两种方式：自定义数组栈和 Java API 中的 Stack 来实现了栈中最小值的功能，保证了在调用栈的 min、push 及 pop 方法时的时间复杂度都是 O(1) 。两种实现方式的代码虽然略不相同，但实现思路都是一样的，都是在元素入栈时判断当前元素是否小于最小元素，如果小于最小元素则先将原最小值入栈，再将当前最小元素入栈，这样当调用 pop 方法时，即使移除的是最小值，只需要将下一个元素取出即为新的最小值了，这样就可以实现调用 min、push 及 pop 方法时的时间复杂度都是 O(1) 了。
最后机智的你一定还有其他的实现答案，评论区告诉我吧~原创不易，各位素质四联，谢啦。大家看完有什么不懂的可以在下方留言讨论.谢谢你的观看。觉得文章对你有帮助的话记得关注我点个赞支持一下！