最小栈

问题拆解

要设计一个栈，除了正常的 push、pop、top，还要能在常数时间里拿到当前栈内的最小值。

难点在最后一句。如果每次 getMin 都遍历一遍栈，那是 O(n)，不达标。如果只用一个变量 min 保存全局最小，push 时好维护，可一旦 pop 掉的正是那个最小值，我就不知道“第二小”是谁了——历史信息已经丢了。

问题的核心是：pop 会让最小值“回退”，所以每一层都得记住“到我为止的最小值”是多少。

辅助栈同步保存最小值快照

我再开一个辅助栈 mins，它和主栈同进同出。每次 push 时，压入 当前值 和 已有最小值 中较小的那个——这就是这一层的“最小值快照”。于是 mins 的栈顶永远等于主栈当前的最小值，pop 时两个栈一起弹，快照自动回退。

这题本身是设计题，用 class 来组织状态最自然：

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        cur_min = val if not self.mins else min(val, self.mins[-1])
        self.mins.append(cur_min)

    def pop(self) -> None:
        self.stack.pop()
        self.mins.pop()

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

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

关键在于两个栈严格同步：任何时刻 len(mins) == len(stack)，mins[i] 表示“前 i+1 个元素的最小值”。这样每一次 pop 都精确地把最小值恢复到上一层的状态。

复杂度

指标	复杂度	原因
push / pop / top / getMin	O(1)	全是栈顶操作
空间	O(n)	辅助栈与主栈等长

可以迁移的模式

• 某个聚合查询（最小、最大）要求 O(1)，但数据会被撤销；
• 用“额外一列快照”把历史信息随数据一起保存、一起回退；
• 空间换时间：多存一份，换来查询不再遍历。

只要操作是“可撤销”的，就想想能不能让每一层自带它需要的答案。