设计一个有getMin功能的栈

【题目】

​ 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

​ 1.pop、push、getMin操作的时间复杂度都是O（1）。

​ 2.设计的栈类型可以使用现成的栈结构。

【思路】

​ 使用两个栈，一个栈a正常的进出，另外一个栈b用来维护最小值，时刻保持b栈的栈顶是当前a栈中的最小值。

​ 方法一【两栈深度不一致】：入栈时，每次入a栈的时候，如果b栈为空，入a栈同时进入b栈，如果入a栈的值比b栈顶大，则不入，反之，进入b栈，更新最小值；出栈时，如果出栈值等于b栈顶，就把b栈顶也出了，更新最小值，反之，b栈不更新。

举例：依次压入3、4、5、1、2、1的过程中，stackData（a）和stackMin（b）的变化如下图所示。

说明：图片来自左神的程序代码面试指南，仅供学习使用。

​ 方法二【两栈深度保持一致】：入栈时，进入a栈时，如果b栈为空，进入b栈，如果b栈不为空且b栈栈顶小于a栈新入栈的值，那么把b栈的栈顶再次入b栈，高度保持一致；出栈时，两个栈同时弹出。

举例：依次压入3、4、5、1、2、1的过程中，stackData（a）和stackMin（b）的变化如下图所示。

【代码】

【Java】

方法一：

package keafmd.accumulate.codeinterviewguide.stackwithgetmin;import java.util.Stack;/** * Keafmd * * @ClassName: getMinStack * @Description: 有最小值的栈 * @author: 牛哄哄的柯南 * @date: 2022-06-20 14:29 */public class MyStack1 {    private Stack<Integer> stacka;    private Stack<Integer> stackb;    public MyStack1(){        stacka = new Stack<>();        stackb = new Stack<>();    }    //入栈    public void push(Integer val){        stacka.push(val);        if(stackb.isEmpty()||val<=getMin()){            stackb.push(val);        }    }    //出栈    public Integer pop(){        if(stacka.isEmpty()){            throw new RuntimeException("Stack is empty!");        }        Integer val = stacka.pop();        if(val.equals(getMin())){            stackb.pop();        }        return val;    }    //获取最小值    public Integer getMin(){        if(stackb.isEmpty()){            throw new RuntimeException("Stack is empty!");        }        return stackb.peek();    }}

方法二：

package keafmd.accumulate.codeinterviewguide.stackwithgetmin;import java.util.Stack;/** * Keafmd * * @ClassName: MyStack2 * @Description: 有最小值的栈 * @author: 牛哄哄的柯南 * @date: 2022-06-20 15:07 */public class MyStack2 {    private Stack<Integer> stacka;    private Stack<Integer> stackb;    public MyStack2(){        stacka = new Stack<>();        stackb = new Stack<>();    }    //入栈    public void push(Integer val){        stacka.push(val);        if(stacka.isEmpty()||val<getMin()){            stackb.push(val);        }else{            stackb.push(getMin());        }    }    //出栈    public Integer pop(){        if(stacka.isEmpty()){            throw new RuntimeException("Stack is empty!");        }        Integer val = stacka.pop();        stackb.pop();        return val;    }    //获取最小值    public Integer getMin(){        if(stackb.isEmpty()){            throw new RuntimeException("Stack is empty!");        }        return stackb.peek();    }}

【总结】

方法一和方法二其实都是用 stackb 栈保存着 stacka 每一步的最小值。共同点是所有操作的时间复杂度都为O（1）、空间复杂度都为O（n）。区别是：方法一中stackb压入时稍省空间，但是弹出操作稍费时间；方法二中stackb压入时稍费空间，但是弹出操作稍省时间。