原文链接: https://leetcode-cn.com/problems/min-stack

英文原文

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

 

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

 

Constraints:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

中文题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

 

示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

 

提示：

• pop、top 和 getMin 操作总是在 非空栈 上调用。

通过代码

高赞题解

题目描述（简单难度）

设计数据结构的题，设计一个栈，除了栈特有的功能，入栈、出栈、查看栈顶元素，还需要增加一个功能，得到当前栈里边最小的元素。

解法一

要实现一个 stack，那么我们还能用 java 自带的 stack 吗？也不用纠结，这道题的关键其实是实现「得到最小值这个功能」，所以为了代码简洁些，我们就直接使用系统自带的 stack 了。

这道题最直接的解法就是我们可以用两个栈，一个栈去保存正常的入栈出栈的值，另一个栈去存最小值，也就是用栈顶保存当前所有元素的最小值。存最小值的栈的具体操作流程如下：

将第一个元素入栈。

新加入的元素如果大于栈顶元素，那么新加入的元素就不处理。

新加入的元素如果小于等于栈顶元素，那么就将新元素入栈。

出栈元素不等于栈顶元素，不操作。

出栈元素等于栈顶元素，那么就将栈顶元素出栈。

举个例子。

入栈 3 

|   |    |   |

|   |    |   |

|_3_|    |_3_|

stack  minStack



入栈 5 ， 5 大于 minStack 栈顶，不处理

|   |    |   |

| 5 |    |   |

|_3_|    |_3_|

stack  minStack



入栈 2 ，此时右边的 minStack 栈顶就保存了当前最小值 2 

| 2 |    |   |

| 5 |    | 2 |

|_3_|    |_3_|

stack  minStack



出栈 2，此时右边的 minStack 栈顶就保存了当前最小值 3

|   |    |   |

| 5 |    |   |

|_3_|    |_3_|

stack  minStack



出栈 5，右边 minStack 不处理

|   |    |   |

|   |    |   |

|_3_|    |_3_|

stack  minStack



出栈 3

|   |    |   |

|   |    |   |

|_ _|    |_ _|

stack  minStack

代码的话就很好写了。

class MinStack {

    /** initialize your data structure here. */

    private Stack<Integer> stack;

    private Stack<Integer> minStack;



    public MinStack() {

        stack = new Stack<>();

        minStack = new Stack<>();

    }



    public void push(int x) {

        stack.push(x);

        if (!minStack.isEmpty()) {

            int top = minStack.peek();

            //小于的时候才入栈

            if (x <= top) {

                minStack.push(x);

            }

        }else{

            minStack.push(x);

        }

    }



    public void pop() {

        int pop = stack.pop();



        int top = minStack.peek();

        //等于的时候再出栈

        if (pop == top) {

            minStack.pop();

        }



    }



    public int top() {

        return stack.peek();

    }



    public int getMin() {

        return minStack.peek();

    }

}

解法二

解法一中用了两个栈去实现，那么我们能不能用一个栈去实现呢？

参考了 这里。

解法一中单独用了一个栈去保存所有最小值，那么我们能不能只用一个变量去保存最小值呢？

再看一下上边的例子。

入栈 3 

|   |   min = 3

|   |     

|_3_|    

stack   



入栈 5 

|   |   min = 3

| 5 |     

|_3_|    

stack  



入栈 2 

| 2 |   min = 2?

| 5 |     

|_3_|    

stack  

如果只用一个变量就会遇到一个问题，如果把 min 更新为 2，那么之前的最小值 3 就丢失了。

怎么把 3 保存起来呢？把它在 2 之前压入栈中即可。

入栈 2 ，同时将之前的 min 值 3 入栈，再把 2 入栈，同时更新 min = 2

| 2 |   min = 2

| 3 |  

| 5 |     

|_3_|    

stack  



入栈 6 

| 6 |  min = 2

| 2 |   

| 3 |  

| 5 |     

|_3_|    

stack  



出栈 6     

| 2 |   min = 2

| 3 |  

| 5 |     

|_3_|    

stack  



出栈 2     

| 2 |   min = 2

| 3 |  

| 5 |     

|_3_|    

stack  

上边的最后一个状态，当出栈元素是最小元素我们该如何处理呢？

我们只需要把 2 出栈，然后再出栈一次，把 3 赋值给 min 即可。

出栈 2     

|   |  min = 3   

| 5 |   

|_3_|    

stack  

通过上边的方式，我们就只需要一个栈了。当有更小的值来的时候，我们只需要把之前的最小值入栈，当前更小的值再入栈即可。当这个最小值要出栈的时候，下一个值便是之前的最小值了。

class MinStack {

    int min = Integer.MAX_VALUE;

    Stack<Integer> stack = new Stack<Integer>();

    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 getMin() {

        return min;

    }

}

解法三

参考 这里，再分享利用一个栈的另一种思路。

通过解法二的分析，我们关键要解决的问题就是当有新的更小值的时候，之前的最小值该怎么办？

解法二中通过把之前的最小值入栈解决问题。

这里的话，用了另一种思路。同样是用一个 min 变量保存最小值。只不过栈里边我们不去保存原来的值，而是去存储入栈的值和最小值的差值。然后得到之前的最小值的话，我们就可以通过 min 值和栈顶元素得到，举个例子。

入栈 3，存入 3 - 3 = 0

|   |   min = 3

|   |     

|_0_|    

stack   



入栈 5，存入 5 - 3 = 2

|   |   min = 3

| 2 |     

|_0_|    

stack  



入栈 2，因为出现了更小的数，所以我们会存入一个负数，这里很关键

也就是存入  2 - 3 = -1, 并且更新 min = 2 

对于之前的 min 值 3, 我们只需要用更新后的 min - 栈顶元素 -1 就可以得到    

| -1|   min = 2

| 5 |     

|_3_|    

stack  



入栈 6，存入  6 - 2 = 4

| 4 |   min = 2

| -1| 

| 5 |     

|_3_|    

stack  



出栈，返回的值就是栈顶元素 4 加上 min，就是 6

|   |   min = 2

| -1| 

| 5 |     

|_3_|    

stack  



出栈，此时栈顶元素是负数，说明之前对 min 值进行了更新。

入栈元素 - min = 栈顶元素，入栈元素其实就是当前的 min 值 2

所以更新前的 min 就等于入栈元素 2 - 栈顶元素(-1) = 3

|   | min = 3

| 5 |     

|_3_|    

stack     

再理一下上边的思路，我们每次存入的是 原来值 - 当前最小值。

当原来值大于等于当前最小值的时候，我们存入的肯定就是非负数，所以出栈的时候就是 栈中的值 + 当前最小值 。

当原来值小于当前最小值的时候，我们存入的肯定就是负值，此时的值我们不入栈，用 min 保存起来，同时将差值入栈。

当后续如果出栈元素是负数的时候，那么要出栈的元素其实就是 min。此外之前的 min 值，我们可以通过栈顶的值和当前 min 值进行还原，就是用 min 减去栈顶元素即可。

public class MinStack {

    long min;

	Stack<Long> stack;



	public MinStack(){

        stack=new Stack<>();

    }



	public void push(int x) {

		if (stack.isEmpty()) {

			min = x;

			stack.push(x - min);

		} else {

			stack.push(x - min);

			if (x < min){

				min = x; // 更新最小值

			}

				

		}

	}



	public void pop() {

		if (stack.isEmpty())

			return;



		long pop = stack.pop();

		

		//弹出的是负值，要更新 min

		if (pop < 0) {

			min = min - pop;

		}



	}



	public int top() {

		long top = stack.peek();

		//负数的话，出栈的值保存在 min 中

		if (top < 0) {

			return (int) (min);

        //出栈元素加上最小值即可

		} else {

			return (int) (top + min);

		}

	}



	public int getMin() {

		return (int) min;

	}

}

上边的解法的一个缺点就是由于我们保存的是差值，所以可能造成溢出，所以我们用了数据范围更大的 long 类型。

此外相对于解法二，最小值需要更新的时候，我们并没有将之前的最小值存起来，我们每次都是通过当前最小值和栈顶元素推出了之前的最小值，所以会省一些空间。

解法四

再分享一个有趣的解法，参考 这里 。

回到最初的疑虑，我们要不要用 java 提供的 stack 。如果不用的话，可以怎么做的？

直接用一个链表即可实现栈的基本功能，那么最小值该怎么得到呢？我们可以在 Node 节点中增加一个 min 字段，这样的话每次加入一个节点的时候，我们同时只要确定它的 min 值即可。

代码很简洁，我直接把代码贴过来吧。

class MinStack {

    class Node{

        int value;

        int min;

        Node next;



        Node(int x, int min){

            this.value=x;

            this.min=min;

            next = null;

        }

    }

    Node head;

    //每次加入的节点放到头部

    public void push(int x) {

        if(null==head){

            head = new Node(x,x);

        }else{

            //当前值和之前头结点的最小值较小的做为当前的 min

            Node n = new Node(x, Math.min(x,head.min));

            n.next=head;

            head=n;

        }

    }



    public void pop() {

        if(head!=null)

            head =head.next;

    }



    public int top() {

        if(head!=null)

            return head.value;

        return -1;

    }



    public int getMin() {

        if(null!=head)

            return head.min;

        return -1;

    }

}

总

虽然题目比较简单，但解法二和解法三真的让人耳目一新，一个通过存储，一个通过差值解决了「保存之前值」的问题，思路很值得借鉴。解法四更像降维打击一样，回到改底层数据结构，从而更加简洁的解决了问题。

之前自己在博客总结的，更多题解可以在原地址 https://leetcode.wang。

统计信息

通过次数	提交次数	AC比率
307954	536023	57.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
滑动窗口最大值	困难
最大栈	简单