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

继续出栈，如下图所示：

由于出栈元素 3 为最小值，因此继续将最小值设置为栈顶元素 8，并将栈顶元素出栈，如下图所示：

这样就剩下最后一个元素了，最后一个元素出栈之后就成空栈了，整个流程就执行完了。

实现代码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]) { 

(责任编辑：admin)