155.最小栈

难度：中等

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素 val 推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-2^31 <= val <= 2^31 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10^4 次

解题思路

要做出这道题目，首先要理解栈结构 先进后出 的性质。

对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。

因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面一定有元素 a, b, c, d。

那么，我们可以在每个元素 a 入栈后，把当前栈内的最小值 m 存储起来，在这之后无论何时，只要栈顶元素是 a，我们都可以确认当前栈内存储的最小值是 m。

按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相对应的最小值 m 时刻保持一一对应。

因此我们可以使用一个辅助栈 min_stack，与元素栈 stack 同步插入与删除，同时存储和每个元素相对应的最小值（当前栈中的最小值）。

算法流程：

push() 方法：
push 元素进 stack 栈顶前：
1. 如果该元素小于 min_stack 栈顶值，说明新元素的加入，会使得栈内最小值发生改变，所以该值 push 进 stack 的同时，也要将该值 push 到 min_stack 的栈顶
2. 如果该元素大于或等于 min_stack 栈顶值，说明新元素的加入，不会使得栈内最小值发生改变，所以该值 push 进 stack 的时候，要将 min_stack 的栈顶元素复制一份再次入栈。
pop() 方法： pop 元素出 stack 栈顶时，我们一并 pop 出 min_stack 的栈顶元素。
上面两个方法的操作，可以保证 min_stack 栈顶元素始终是当前 stack 中的最小值。
getMin() 方法：检索 min_stack 栈顶元素即可。

我的代码（辅助栈法）

java

class MinStack {
    Deque<Integer> stack;// 主栈，用于存储所有元素
    Deque<Integer> minStack;// 辅助栈，用于存储每个元素入栈时的最小值

    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
    }

    public void push(int val) {
        // 如果辅助栈为空，或新元素小于等于辅助栈顶元素，则将新元素推入辅助栈
        // 否则，再次将辅助栈顶元素推入辅助栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
        stack.push(val);// 将元素推入主栈
    }

    public void pop() {
        // 同时从两个栈中弹出栈顶元素
        minStack.pop();
        stack.pop();
    }

    public int top() {
        // 返回主栈顶元素
        return stack.peek();
    }

    public int getMin() {
        // 返回辅助栈顶元素，即当前栈中的最小值
        return minStack.peek();
    }
}

时间复杂度：题目中的所有操作，时间复杂度均为 O(1)

空间复杂度：O(n)

总结

栈的实现通常有两种：

使用数组模拟栈
使用系统自带的栈结构

155.最小栈 ​

解题思路 ​

我的代码（辅助栈法） ​

总结 ​

155.最小栈

解题思路

我的代码（辅助栈法）

总结