关阿姨带你横扫LeetCode系列之最小栈

关阿姨正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

首先跟大家阐明一点就是，每道算法题都有多种解法，我们只讲LeetCode上几种优秀的解题思路~，希望

可以帮助到大家，那我们先来看下题目描述吧~

一、题目描述：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

二、思路分析：

首先，我们知道栈是先进后出的，那么如果一个元素 a 在入栈时，栈里已经有元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中；这样的话我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是a，我们就可以直接返回存储的最小值 m。根据这个思路，我们就可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

三、代码总结

class MinStack {
    Deque<Integer> myStack;
    Deque<Integer> minStack;
    public MinStack(){
        myStack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }
    public void push(int x){
        myStack.push(x);
        minStack.push(Math.min(minStack.peek(),x));
    }
    //删除栈顶元素
    public void pop(){
        myStack.pop();
        minStack.pop();
    }
    //获取栈顶元素
    public int top(){
        return myStack.peek();
    }
    //获取最小元素
    public int getMin(){
        return minStack.peek();
    }
}
复制代码