Min Stack

155. Min Stack

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

• push(x) -- Push element x onto stack.

• pop() -- Removes the element on top of the stack.

• top() -- Get the top element.

• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

My Solutions:

1。 方法1：用两个stack。一个栈来按顺序存储 push 进来的数据，另一个栈去存最小值，也就是用栈顶保存当前所有元素的最小值。必须要用另一个stack保存最小值的原因是，当最小的值被pop出去，次小的值必须在最顶端。

push：stack 直接push，这个元素和minStack里peek的值比较：

• 如果新加入的元素大于栈顶元素，不操作

• 如果新加入的元素小于等于栈顶元素，pop进minStack

pop：记录下stack直接pop的值，然后：

• 如果这个值不是minStack里的最小值，不操作。

• 如果这个值也是minStack里的最小值，minStack也pop。

top：stack 直接peek。

getMin：

• 如果minStack不为空，从minStack peek

• 如果minStack为空，从stack peek

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

作者：windliang
链接：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/

class MinStack {
    Stack<Integer> stack, minStack;
    
    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }
    
    public void push(int x) {
        stack.push(x);
        if (!minStack.isEmpty()) {
             //"<=" for duplicate numbers
            if (x <= minStack.peek()) minStack.push(x); 
        } else {
            minStack.push(x);
        }
    }
    
    public void pop() {
        int x = stack.pop();
        if (!minStack.isEmpty()) {
            if (x == minStack.peek()) minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        if (!minStack.isEmpty()) return minStack.peek();
        else return stack.peek();
    }
}

2。 方法2：用一个stack，和一个int min存最小值。

push：先比较当前值和min，如果当前值比现有的min小，先把现有的min push进去，更新min为当前值。最后再push当前值。这样保证stack的最顶端一定是最小值。同时，当最小的值被pop出去，次小的值在最顶端，这样就知道此时最小值是多少。

pop：pop出来的值等于min，则需要再pop一次，把这个min的值更新。

top：stack直接peek

getMin：直接返回min

入栈 3，3比MAX_INTEGER小，把max和3依次push进去，min=3
|   |    
|   |    
| 3 | 
|MAX|   
stack  

入栈 5，5 大于 min，直接push进去5，min=3
|   |    
| 5 |    
| 3 |
|MAX|       
stack  

入栈 2 ，2比min小，先把min=3 push进去，再push2，min=2
| 2 | 
| 3 |    
| 5 |    
| 3 |
|MAX|       
stack 

出栈 2，pop出来的值2等于min，则需要再pop一次出来3，更新min=3  
| 5 |    
| 3 |
|MAX|       
stack 

出栈 5
|   |    
| 3 |
|MAX|       
stack 

出栈 3
|   |    
|   |    
|MAX|    
stack  

class MinStack {

    Stack<Integer> stack;
    int min;
    
    public MinStack() {
        stack = new Stack<Integer>();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) { 
         if (x <= min) {
            stack.push(min); //在stack上加一个当前的最小数
            min = x; //更新最小数
        }
        stack.push(x);
    }
    
     //if pop out the min, set the min to be the second smallest
    public void pop() {
        if (min == stack.pop()) min = stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }
}