最小栈

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

实现 MinStack 类：

• MinStack() 初始化堆栈对象。
• void push(int value) 将元素 value 推入堆栈。
• 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 <= value <= 2^31 - 1
• pop、top 和 getMin 操作总是在非空栈上调用
• push、pop、top 和 getMin 最多被调用 3 * 10^4 次

辅助栈：

class MinStack {
private:
    stack<int> stk;
    stack<int> minStk;

public:
    MinStack() {

    }

    void push(int value) {
        stk.push(value);

        if (minStk.empty())
        {
            minStk.push(value);
        }
        else
        {
            minStk.push(min(value, minStk.top()));
        }
    }

    void pop() {
        stk.pop();
        minStk.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return minStk.top();
    }
};

核心思想

普通栈只能在 O(1) 时间拿到栈顶元素。

但如果想知道整个栈里的最小值，直接做法是每次 getMin 都遍历一遍栈，这样时间复杂度是 O(n)，不满足题目要求。

要让 getMin 也是 O(1)，就需要在压栈的时候同步记录“当前栈内的最小值”。

这题最关键的观察是：

对于栈中的每一层，都记录从栈底到这一层为止的最小值，那么栈顶对应的最小值就是当前整个栈的最小值。

所以可以维护两个栈：

• stk：正常保存所有入栈元素
• minStk：保存每一层对应的当前最小值

两个栈始终保持相同的大小。

当 stk 弹出一个元素时，minStk 也弹出对应层的最小值。

辅助栈存什么

minStk 的第 i 个元素表示：

stk 中从栈底到第 i 个元素这一段的最小值。

也就是说，如果当前 stk 是：

[-2, 0, -3]

那么 minStk 是：

[-2, -2, -3]

每一层都对应当前前缀栈的最小值。

因此，当前整个栈的最小值就是：

minStk.top()

操作逻辑

push

先把 value 放入普通栈：

stk.push(value)

然后更新辅助栈。

如果 minStk 为空，说明这是第一个元素，它自己就是最小值。

否则，当前最小值应该是：

min(value, minStk.top())

也就是新元素和之前最小值中的较小者。

pop

stk 弹出栈顶元素时，minStk 也必须同步弹出。

因为 minStk.top() 记录的是当前这一层对应的最小值。

如果只弹出 stk，不弹出 minStk，辅助栈里的最小值就会和真实栈状态不匹配。

top

栈顶元素直接返回：

stk.top()

getMin

因为 minStk.top() 始终保存当前整个栈的最小值，所以直接返回：

minStk.top()

为什么重复最小值也能处理

如果栈中出现多个相同的最小值，辅助栈按层记录最小值，不会丢失重复信息。

例如依次执行：

push(2)
push(1)
push(1)

此时：

stk    = [2, 1, 1]
minStk = [2, 1, 1]

弹出一个 1 以后：

stk    = [2, 1]
minStk = [2, 1]

getMin() 仍然返回 1，结果正确。

这也是为什么辅助栈不能只在遇到更小值时简单记录一次最小值。

按层同步记录，可以自然处理重复最小值。

边界情况

如果栈中只有一个元素，那么 stk 和 minStk 都只有一个元素。

此时 top() 和 getMin() 都会返回这个元素。

如果新压入的元素比当前最小值更大，minStk 仍然会压入原来的最小值。

这样即使后面弹出较大的元素，当前最小值也不会变化。

如果新压入的元素比当前最小值更小，minStk 压入这个新元素。

它会成为新的当前最小值。

题目保证 pop、top 和 getMin 总是在非空栈上调用，所以代码中不需要额外处理空栈返回值。

正确性证明

我们证明：算法能够正确实现 push、pop、top 和 getMin，并且 getMin 返回当前栈中的最小元素。

结论 1：两个栈始终保持相同大小

初始化时，stk 和 minStk 都为空，大小相同。

每次执行 push，算法都会向 stk 压入一个元素，同时向 minStk 压入一个当前最小值。

每次执行 pop，算法都会同时弹出 stk 和 minStk 的栈顶。

因此任意时刻，两个栈的大小始终相同。

结论 2：minStk 的每一层都保存对应前缀栈的最小值

当压入第一个元素时，minStk 中压入它本身。

这显然是当前栈的最小值。

假设压入新元素 value 之前，minStk.top() 已经是原栈中的最小值。

压入 value 之后，新栈的最小值只可能是两者之一：

• 原栈中的最小值
• 新压入的 value

所以新栈最小值就是：

min(value, minStk.top())

算法正是把这个值压入 minStk。

因此，minStk 的每一层都正确保存了对应前缀栈的最小值。

结论 3：getMin 返回当前栈中的最小值

由结论 1 可知，minStk 的栈顶和 stk 的栈顶处在同一层。

由结论 2 可知，minStk 栈顶保存的是从栈底到当前栈顶这一整段的最小值。

这正是当前整个栈中的最小元素。

所以 getMin() 返回 minStk.top() 是正确的。

结论 4：top 和 pop 不会破坏最小值记录

top() 只读取 stk.top()，不会修改任何结构，所以不会影响栈状态。

pop() 会删除 stk 的栈顶元素，同时删除 minStk 中对应这一层的最小值。

弹出后，新的 minStk.top() 正好对应新的 stk.top() 这一层。

所以弹出操作后，辅助栈仍然正确记录当前栈的最小值。

得出结论

由结论 1 可知，两个栈始终一一对应。

由结论 2 可知，辅助栈每一层都保存正确的当前最小值。

由结论 3 可知，getMin 的返回值正确。

由结论 4 可知，top 和 pop 不会破坏这个关系。

因此算法正确实现了 MinStack。

举例理解

以示例操作为例。

可以看到，辅助栈的栈顶始终就是当前普通栈中的最小值。

复杂度分析

每个操作都只进行了常数次栈操作。

所以时间复杂度是：

O(1)

辅助栈会为每个普通栈元素保存一个对应的最小值。

所以空间复杂度是：

O(n)

其中 n 是栈中元素个数。