一、栈获取最小值算法概述

获取栈的最小值算法：可以动态的获取一个栈中元素的最小值，动态的意思是，当该栈发生push或者pop操作，可能会导致最小值发生改变。实现该算法需要用到一个辅助栈，专门用于保存栈的最小值动态变化值。
实现步骤如下：

• 需要借助一个辅助栈，minStack，主栈为mainStack，初始两个栈都是空栈。

• 当需要往mainStack插入元素时，如果minStack为空，直接插入。

• 如果minStack不为空，则将要插入的元素elem与minStack.peek()进行比较，若elem<minStack.peek(),则同时插入到minStack和mainStack，若elem>minStack.peek()，则elem照常插入到mainStack当中，然后将minStack.push(minStack.peek())

• 当mianStack弹出元素时，minStack也同步弹出。

• 取mianStack当前最小值直接minStack.peek()就好了。

二、栈获取最小值算法实现

import java.util.Stack;

public class MinStack {
    Stack<Integer> minStack;
    Stack<Integer> mianStack;
    public MinStack(){
        this.minStack = new Stack<Integer>();
        this.mianStack = new Stack<Integer>();
    }

    public void push(Integer elem){
        if (minStack.isEmpty() && mianStack.isEmpty()){
            mianStack.push(elem);
            minStack.push(elem);
        }else if (elem < minStack.peek()){
            mianStack.push(elem);
            minStack.push(elem);
        }else if (elem > minStack.peek()){
            mianStack.push(elem);
            minStack.push(minStack.peek());
        }
    }

    public void pop(){
        if (mianStack.isEmpty() && minStack.isEmpty()){return;}
        mianStack.pop();
        minStack.pop();
    }

    public Integer getMinElem(){
        if (minStack.isEmpty()){return null;}
        else{
            return minStack.peek();
        }
    }

    public String toString(){
        return minStack.toString();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(4);
        minStack.push(3);
        minStack.push(5);
        System.out.println(minStack.toString());
        System.out.println(minStack.getMinElem());
    }
}

三、图例说明算法运行步骤

3.1、初始状态为

image.png

3.2、插入一个元素5

image.png

3.3、在插入一个元素4

image.png

3.4、在插入一个元素7

image.png

3.5、在插入一个元素2

image.png

3.6、弹出一个元素

image.png

其实可以发现不管main怎么操作，无论处于什么状态，在minStack对应位置，都是mainStack的最小值。