实现代码1
接下来我们将上面的思路用代码实现一下，我们用数组实现的栈来实现相关的功能，代码如下：
class MinStack { private int[] data; // 栈数据 private int maxSize; // 最大长度 private int top; // 栈顶指针（下标） private int min; // 最小值 // 构造函数 public MinStack() { // 设置默认值 maxSize = 10000; data = 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<Integer> 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) 了。
最后
机智的你一定还有其他的实现答案，评论区告诉我吧~
