好的，我们这次来详细讲解 LeetCode 第 155 题「最小栈」。
这道题虽然看起来简单，但设计思路很巧妙，能帮助我们理解数据结构设计的思维。

1. 题目描述

设计一个栈，除了支持普通的栈操作（push、pop、top）之外，还要能在 常数时间 内检索到栈中的最小元素。

实现 MinStack 类：

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素 val 推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

要求：每个操作（包括 getMin）的时间复杂度为 O(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. 思路分析

2.1 为什么不能只用单个变量存最小值？

如果只用一个变量 minValue 记录当前最小值，当最小值在栈顶被弹出后，新的最小值是多少？
我们无法立刻知道，除非遍历栈中剩余元素，但遍历是 O(n) 的，不符合 O(1) 的要求。

2.2 核心难点

• 栈的 pop 操作可能移除当前的最小值，因此需要能快速知道 次小值。
• 必须保证在任何操作后，都能在 O(1) 时间内得到当前栈的最小值。

2.3 常见思路：辅助栈

我们可以维护两个栈：

• 主栈 stack：正常存放所有元素。
• 最小栈 minStack：存放当前主栈中对应的最小值。

规则：

1. 当 push(val) 时：
   • 主栈直接压入 val。
   • 最小栈压入 min(val, minStack的栈顶)，这样最小栈的栈顶始终是当前主栈中的最小值。
2. 当 pop() 时：
   • 主栈和最小栈同时弹出栈顶。
3. 当 getMin() 时：
   • 直接返回最小栈的栈顶。

这样，最小栈与主栈高度相同，每个位置的最小栈元素表示 主栈从底到该位置的最小值。

3. 逐步推演示例

我们以题目示例来走一遍流程。

初始：

stack:    []
minStack: []

push(-2):

stack:    [-2]
minStack: [-2]   （当前最小值是 -2）

push(0):

stack:    [-2, 0]
minStack: [-2, -2]  （min(-2, 0) = -2，所以最小栈压入 -2）

push(-3):

stack:    [-2, 0, -3]
minStack: [-2, -2, -3]  （min(-2, -3) = -3）

getMin():

• 查看 minStack 栈顶 = -3 ✅

pop():

stack:    [-2, 0]
minStack: [-2, -2]

top():

• 返回 stack 栈顶 0 ✅

getMin():

• 返回 minStack 栈顶 -2 ✅

4. 代码实现（Python）

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.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.stack.pop()
        self.min_stack.pop()

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

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

5. 复杂度分析

• 时间复杂度：所有操作 O(1)。
• 空间复杂度：O(n)，因为用了两个栈，每个元素最多存两份（最坏情况是降序序列，最小栈和主栈相同）。

6. 另一种优化空间的方法

如果不想在最小栈存那么多重复值，可以改为：

• 最小栈只存 更小或等于当前最小值 的情况，并在 pop 时判断是否从最小栈也弹出。

但这样代码会稍复杂，需要判断相等的情况，避免提前弹出最小值。基础解法用同步栈更直观易懂。

7. 总结

这道题的关键是 用辅助栈同步记录每个状态下的最小值，这样在 pop 后能立刻知道剩余栈的最小值，满足 O(1) 取最小值的要求。
这是数据结构设计中“空间换时间”的典型例子。

希望这个一步步的讲解能让你彻底明白！如果还有疑问，我们可以继续探讨。