155.最小栈

• 本题核心是 实现得到栈中最小值的方法

原文：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/

双辅助栈

思路

• 一个栈保存正常的入栈出栈的元素，另一个栈去存最小值，即该栈的栈顶 保存当前栈中所有元素的最小值。

• 具体步骤

  • 将第一个元素入栈。

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

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

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

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

• 实例

  入栈 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
  

代码

    /*
     * 6ms
     */
	
    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();
    }
}

单辅助栈 单变量存储min

• 相对于双辅助栈 ，使用变量min存储最小值 (分析思路很妙)
• 实例

入栈 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  

代码

/*
 * 6ms
 */
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值 且每次在链表头部加入节点

代码

/*
 * 5ms
 */
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-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/

155.最小栈

原文：https://www.cnblogs.com/yh-simon/p/12879137.html