输入操作序列：  
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()  
输出结果：  
null, null, null, -3, null, 0, -2  

class MinStack:
    def __init__(self):
        self.data_stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.data_stack.append(val)
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))

    def pop(self) -> None:
        self.data_stack.pop()
        self.min_stack.pop()

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

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

LeetCode 第 155 题：最小栈（Min Stack） 题目描述 设计一个栈，除了支持常规的入栈（push）、出栈（pop）、查看栈顶元素（top）操作外，还需要支持在 常数时间 内检索到栈中最小元素的 getMin 方法。 示例 解题思路 普通栈的 push 、 pop 、 top 都是 O(1) 时间，但 getMin 如果遍历栈则需要 O(n)。为了 O(1) 时间得到最小值，我们需要 额外维护一个结构 ，时刻记录当前栈的最小值。 方法 1：辅助栈（最小栈同步） 使用两个栈： dataStack ：正常保存所有元素。 minStack ：保存当前 dataStack 中对应位置的最小值。 push(x) 操作 ： 将 x 压入 dataStack 。 比较 x 与 minStack 栈顶元素（如果 minStack 为空则直接压入 x），将 较小值 压入 minStack 。 pop() 操作 ： 同时弹出 dataStack 和 minStack 的栈顶。 top() 操作 ： 返回 dataStack 的栈顶。 getMin() 操作 ： 返回 minStack 的栈顶。 例子演示 操作序列：push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() | 操作 | dataStack | minStack | 说明 | |------------|-----------|----------|------| | push(-2) | [ -2] | [ -2 ] | minStack 压入 -2 | | push(0) | [ -2,0] | [ -2,-2 ] | 0 与 -2 比，minStack 压入 -2 | | push(-3) | [ -2,0,-3] | [ -2,-2,-3 ] | -3 与 -2 比，minStack 压入 -3 | | getMin() | | | 返回 minStack 栈顶 -3 | | pop() | [ -2,0] | [ -2,-2 ] | 同时弹出 dataStack 和 minStack 栈顶 | | top() | | | 返回 dataStack 栈顶 0 | | getMin() | | | 返回 minStack 栈顶 -2 | 优点 ：简单直观，O(1) 时间所有操作，O(n) 额外空间。 方法 2：辅助栈（非同步，节省空间） 如果连续压入的元素都比当前最小值大， minStack 不需要每次压入新元素，可以 只在 x ≤ 当前最小值时才压入 minStack 。 push(x) ： 压入 dataStack 。 如果 minStack 为空 或 x ≤ minStack 栈顶，则压入 minStack 。 pop() ： 弹出 dataStack 栈顶 y。 如果 y 等于 minStack 栈顶，则弹出 minStack 。 例子演示 （同上操作序列） | 操作 | dataStack | minStack | 说明 | |------------|-----------|----------|------| | push(-2) | [ -2] | [ -2 ] | minStack 压入 -2 | | push(0) | [ -2,0] | [ -2 ] | 0 > -2，minStack 不变 | | push(-3) | [ -2,0,-3] | [ -2,-3 ] | -3 ≤ -2，minStack 压入 -3 | | getMin() | | | 返回 -3 | | pop() | [ -2,0] | [ -2 ] | 弹出 -3，它等于 minStack 栈顶，所以 minStack 也弹出 | | top() | | | 返回 0 | | getMin() | | | 返回 -2 | 优点 ：在压入元素较大时， minStack 元素较少，节省空间。 代码实现（方法 1：同步版本） 总结 核心思想：用辅助栈保存每个状态下的最小值。 同步版本简单不易出错，非同步版本可节省空间。 所有操作时间复杂度 O(1)，空间复杂度 O(n)。