取最小值不用扫全栈:最小栈把历史最低点也压了进去

最小栈是在普通后进先出栈上再加一个 getMin,要求 push、pop、top、getMin 全部常数时间。它之所以能做到,是因为每个栈深度都保存了「从栈底到这里的元素最小值」这张快照,弹栈只是回到上一层的快照,根本不需要重新扫描。最常见的误区是只维护一个 min 变量,弹出最小值后就再也找不到第二小;另一个误区是把差值编码说成 O(1) 空间,其实总空间仍是 O(n),还受整数溢出与类型限制。读完你能写对重复最小值的处理,讲清最小栈与单调栈的区别,并在面试和生产里选对实现。

是什么

最小栈(Min Stack)是一种在普通栈的 push、pop、top 之外,再提供一个 getMin 的抽象数据类型,并且要求这四个操作都是 O(1)。它不改变后进先出的顺序,只是在每一次压栈时,顺手把「截至当前栈顶的最小值」也记下来。

一句话直觉:它不是在取最小值时算得快,而是在压栈时就把答案抄在了每一层上,取的时候只看栈顶那张便签。

典型场景是「带撤销的历史最值」:例如按时间顺序记录成交价,随时要知道自开盘以来的最低价,同时允许撤掉最近一笔;或者深度优先搜索一条路径,随时查询路径上的最小边权,回溯时自动恢复。面试里它也是高频题(LeetCode 155),但真正被追问的是重复最小值、空间上界与「不用辅助栈」这三个点。

核心原理

先看暴力做法:每次 getMin 都从栈顶扫到栈底,单次 O(n);如果调用 n 次,总代价 O(n²)。信息其实早就有了,只是没有存。

关键不变量是:栈的每一层都携带一个「前缀最小值」,即从栈底到该层所有元素的最小值。当新元素 x 压入深度 d 时,新的前缀最小值只可能来自两个候选——上一层的前缀最小值,或者 x 本身,取较小者即可。它不需要知道整个栈的内容,这是一次可以增量维护的折叠(fold)。

弹栈为什么能自动恢复?因为 LIFO 恰好把「历史」按相反顺序保留了下来。弹出栈顶,等于撕掉最新的一张便签,露出来的上一张就是压入该元素之前的最小值。类比一支登山队,每到一个营地就在路标上写下「到目前为止的最低海拔」;下撤时依次经过旧营地,看到的就是当时的最低点,不必重新测一遍。

实现有两条常见路线。第一条是每个元素存成 (value, min_so_far) 的二元组;第二条是数据栈加一个辅助的最小值栈。辅助栈可以和数据栈等高,也可以只在出现「小于等于当前最小值」的元素时才压入,后者在随机数据上更省,但最坏仍是 O(n)。

class MinStack:
    def __init__(self):
        self.data = []
        self.mins = []              # 栈顶是当前 data 的最小值

    def push(self, x: int) -> None:
        self.data.append(x)
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)     # 用 <=,重复的最小值也要记一份

    def pop(self) -> None:
        if self.data.pop() == self.mins[-1]:
            self.mins.pop()

    def top(self) -> int:
        return self.data[-1]

    def getMin(self) -> int:
        return self.mins[-1]

这里每个元素进 data 一次、进 mins 至多一次,出栈同理,所以均摊 O(1),总空间 O(n)。mins 的额外空间取决于数据形态:严格递增时只有栈底一个元素,严格递减时会有 n 个。

辅助栈还有一个容易讲漏的性质:从栈底到栈顶,mins 里的值单调不增。压栈只可能让它更小或保持不变,弹栈只可能让它变大或保持不变,所以 getMin 永远只读栈顶,不需要在辅助栈里再做一次查找。

有人会追问:既然要取最小,为什么不用小顶堆?因为 pop 的语义是删掉最后进来的元素,而堆只能高效删掉最小值;要删指定的栈顶,得先定位再调整,代价 O(log n),还要额外处理重复值。平衡树能同时支持取最小和删任意元素,但仍是 O(log n),并没有利用 LIFO 这个顺序。最小栈的价值正在于此:它把「历史顺序」变成了免费的索引。

还有第三种「差值编码」写法:只用一个栈和一个 min 变量,压栈时存 x 与当前 min 的差;如果 x 更小就更新 min,差值存成负数,弹栈时用负数把旧 min 反推回来。它省掉的只是那一个辅助容器,栈本身仍然有 n 个元素,所以总空间依旧是 O(n),并不是很多人以为的 O(1) 总空间。

常见考点与误区

  • 只维护一个 min 变量。 这是最典型的错法:push 3、1、2 之后 min 是 1,pop 掉 1 再 getMin,答案应该是 3,但变量里只剩 1。最小值会随弹栈失效,必须保留每个历史深度的副本。
  • 重复最小值用了严格小于。 如果只在 x < 当前最小值时压辅助栈,然后 pop 时用「等于」判断,那么 push 2、1、1 再 pop 一次,辅助栈里的 1 会被误弹,getMin 立刻失去正确答案。要么用 <= 压入、相等时弹,要么每个元素都存一份前缀最小值,别把两个条件混搭。
  • 把差值编码说成 O(1) 空间。 面试官问「能不能不用辅助栈」,想听的是「辅助空间可以降到 O(1),总空间仍是 O(n),而且要用 64 位防溢出、只适用于整数」。用 32 位存 x - min,在 INT_MAX 与 INT_MIN 相邻时就会溢出,这是这个技巧真正的边界。
  • 和单调栈混为一谈。 单调栈为了求下一个更大元素,会把「永远不可能再成为答案」的元素直接弹掉;最小栈不能这么做,因为被弹掉的元素还要按 LIFO 顺序回来。比如 push 3、1、2,单调栈在压入 1 时就丢了 3,而最小栈弹出 2、1 之后必须能答出 3。
  • 空栈行为没有定义。 top 和 getMin 在空栈上该抛异常还是返回哨兵值,是接口契约的一部分;很多实现只在正常路径测试过,线上第一次空栈调用才炸。
  • 复杂度的口径说不清。 用动态数组实现时,push 偶尔要扩容搬移,严格说是均摊 O(1) 而不是每次最坏 O(1);对尾延迟敏感的场景,这一点会被追问。

实践建议

  • 默认选「数据栈 + 前缀最小值」的清晰写法,每个元素存二元组或两个平行数组都行。可读性远比省那点辅助空间重要;只有值域明确、内存确实吃紧,才考虑差值编码,并统一升到 64 位整数。
  • 先确认你要的是哪种「极值」。 最小栈只适用于后进先出的历史;如果要在滑动窗口或队列上取最小值,应该用单调双端队列;如果要任意区间的最小值,用稀疏表或线段树。拿最小栈硬套窗口,会在左端过期时无从下手。
  • 长期运行的服务要盯容量。 辅助栈在最坏情况下与数据栈等高,若历史只增不减,内存会线性上涨;给栈设上限、定期快照,或者只保留业务真正需要的深度。Java 里用 ArrayDeque 加基本类型数组,避免 Integer 装箱和用 == 比较对象。
  • 并发场景别只给每个方法加锁。 「先 getMin 再 pop」是一个复合操作,两个方法各自线程安全也挡不住中间被插队;需要把整段逻辑放进同一把锁,或改用不可变快照。
  • 测试要覆盖形态而不是只覆盖 happy path。 至少测空栈契约、单元素、全相同、严格递减、先降后升再弹,以及整数边界;再写一个 brute-force 对拍,随机交错 push、pop、getMin,比较每次输出。

一句话总结:最小栈的 O(1) 不是算得更快,而是把每个深度上的最小值提前存成了快照,弹栈只是退回上一张。

相关阅读

← 返回文章志