categories: [Blog,Algorithm]

155. 最小栈

难度简单820
设计一个支持 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 操作总是在 非空栈 上调用。
  1. class MinStack {
  3.     Deque<Integer> xStack;
  4.     Deque<Integer> minStack;
  6.     public MinStack() {
  7.         xStack = new LinkedList<Integer>();
  8.         minStack = new LinkedList<Integer>();
  9.         minStack.push(Integer.MAX_VALUE);//
  10.     }
  12.     public void push(int x) {
  13.         xStack.push(x);
  14.         minStack.push(Math.min(minStack.peek(), x));
  15.     }
  17.     public void pop() {
  18.         xStack.pop();
  19.         minStack.pop();
  20.     }
  22.     public int top() {
  23.         return xStack.peek();
  24.     }
  26.     public int getMin() {
  27.         return minStack.peek();
  28.     }
  30. // 作者：LeetCode-Solution
  31. // 链接：https://leetcode-cn.com/problems/min-stack/solution/zui-xiao-zhan-by-leetcode-solution/
  32. }
  34. /**
  35.  * Your MinStack object will be instantiated and called as such:
  36.  * MinStack obj = new MinStack();
  37.  * obj.push(x);
  38.  * obj.pop();
  39.  * int param_3 = obj.top();
  40.  * int param_4 = obj.getMin();
  41.  */

解析

辅助栈
要做出这道题目，首先要理解栈结构先进后出的性质。
对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。
那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
image.png