跳到主要内容

LeetCode 155. 最小栈

本节目标

为每层栈状态同步保存当前最小值，使四个操作都保持常数时间。

设计支持 push、pop、top 和 getMin 的栈，并要求每个操作均为 O(1)。普通栈能在栈顶完成前三个操作，却不能直接知道最小值。这道题是栈与队列中“主状态与辅助状态同步”的母题。

查看原题

为什么不能在查询时扫描​

每次 getMin 都遍历整个栈确实能得到答案，但一次查询需要 O(n)。题目要求常数时间，说明最小值必须在 push 时提前维护好，而不是在查询时再计算。

关键是：栈的每一层都对应一个历史状态。把某层压入后，它以下所有元素不变；因此该层的最小值可以由当前值和上一层的最小值立即得到。

每层保存当前最小值​

栈元素保存为 (value, currentMinimum)。压入 value 时，将它与旧栈顶的最小值比较，得到新层的 currentMinimum。弹出时两个值一起移除；新的栈顶已经保存了此前状态对应的最小值。

重复最小值也必须逐层保存。例如压入 -2, -2 后弹出一个 -2，剩下的一层仍要返回 -2。如果只在严格变小时记录辅助值，弹出后会错误地丢失这个答案。

代码实现​

两种语言都用一组二元组保存栈层。题目保证 pop、top 和 getMin 不会在空栈上调用，因此实现只保留平台规定的操作，不额外定义空栈异常协议。

C++17
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

class MinStack {
public:
    void push(int val) {
        int minimum = values.empty() ? val : min(val, values.back().second);
        values.push_back({val, minimum});
    }

    void pop() {
        values.pop_back();
    }

    int top() {
        return values.back().first;
    }

    int getMin() {
        return values.back().second;
    }

private:
    // 每层同时保存当前最小值，重复最小值也不能省略
    vector<pair<int, int>> values;
};

复杂度分析​

四个操作都只读取、写入或删除栈顶的一层，时间复杂度均为 O(1)。每个压入值额外保存一个最小值，空间复杂度为 O(n)。

易错点​

  • getMin 时重新遍历整个栈，无法满足常数时间要求。
  • 只维护一份当前最小值，弹出最小值后无法恢复之前的值。
  • 忽略重复最小值：辅助状态应在每一层保存，而非只在最小值变小时保存。

模式迁移​

当数据结构需要在常规读写外快速回答“当前最大值、最小值、前缀和或其他聚合状态”时，可以问辅助状态能否随每一步操作同步更新。单调队列和带前缀信息的栈都是同一思路的延伸。