好的，我们这次来详细讲解 LeetCode 第 155 题：最小栈（Min Stack）。
这道题是学习数据结构设计的一个经典入门题，它看似简单，但要想高效地实现其核心功能，需要一些巧妙的思考。
第一步：题目描述
题目要求：
设计一个支持 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.
第二步：问题核心与难点分析
我们先来理解一下为什么这道题不简单。
- 栈的基本操作：
push、pop、top是栈的标准操作，用任何语言的基本数据结构（如数组、链表）都很容易实现，时间复杂度也是O(1)。 - 真正的挑战：难点在于
getMin()操作。如果我们只是在需要最小值时才去遍历整个栈，那么时间复杂度是O(n)，这违反了题目O(1)的要求。 - 关键矛盾：当我们执行
pop操作时，如果被弹出的元素恰好是当前的最小值，那么最小值就发生了变化。我们必须能够 立即知道 新的最小值是什么，而不能重新扫描。
所以，我们需要设计一种方法，能够 动态地、随时地 记录下当前栈状态下的最小值。
第三步：解决方案思路演进
我们来一步步思考如何解决这个核心矛盾。
思路一：暴力法（不可行）
- 方法：在
MinStack类内部维护一个标准的栈stack来存储数据。当调用getMin()时，遍历整个stack来找到最小值。 - 缺点：
getMin()操作的时间复杂度为O(n)，不满足题目要求。直接否决。
思路二：使用一个变量记录最小值（不完善）
- 方法：用一个变量
min_val来记录当前的最小值。push(val)时，如果val < min_val，就更新min_val = val。getMin()时，直接返回min_val。
- 问题：当我们
pop()一个元素时，如果弹出的正好是min_val，那么我们就丢失了之前的最小值信息，无法确定新的最小值是多少。例如，栈内元素为[5, 2, 1]，min_val是 1。pop()之后，栈变成[5, 2]，新的最小值应该是 2，但我们无法从min_val中得到这个信息。
思路三：辅助栈法（最优解）
这是最经典和直观的解决方案。我们使用 两个栈。
- 主栈 (
stack)：用于正常存储所有压入的元素，支持push、pop、top。 - 辅助栈 (
min_stack)：专门用来存储 主栈每个状态 下对应的最小值。
它们如何协同工作？
-
push(val)操作：- 将
val压入 主栈。 - 判断是否要压入 辅助栈：
- 如果 辅助栈为空（说明是第一个元素），那么
val自然是最小值，将其也压入辅助栈。 - 如果 辅助栈不为空，则比较
val和 当前辅助栈栈顶 的值（即当前最小值）。 - 如果
val小于等于 当前最小值，则将val也压入辅助栈。 - 否则（
val大于当前最小值），辅助栈 不做任何操作。
- 如果 辅助栈为空（说明是第一个元素），那么
为什么是“小于等于”？这是为了处理重复最小值的情况，确保每个最小值都被记录，弹出时不会提前丢失。
- 将
-
pop()操作：- 弹出 主栈 的栈顶元素。
- 判断这个被弹出的元素是否等于 当前辅助栈栈顶 的值（即当前最小值）。
- 如果 相等，那么说明我们弹出了一个最小值，所以也需要将 辅助栈 的栈顶弹出。这样，辅助栈新的栈顶就是之前次小的值，也就是新的最小值。
- 如果 不相等，则辅助栈保持不变。
-
top()操作：直接返回 主栈 的栈顶元素。 -
getMin()操作：直接返回 辅助栈 的栈顶元素。因为这个栈顶永远记录着当前主栈状态下的最小值。
让我们用题目示例来走一遍流程：
操作序列: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
| 操作 | 主栈 (stack) | 辅助栈 (min_stack) | 说明 |
|---|---|---|---|
| 初始化 | [] | [] | |
push(-2) |
[-2] | [-2] | 辅助栈空，-2入栈。 |
push(0) |
[-2, 0] | [-2] | 0 > -2，辅助栈不变。 |
push(-3) |
[-2, 0, -3] | [-2, -3] | -3 < -2，-3入辅助栈。 |
getMin() |
[-2, 0, -3] | [-2, -3] | 返回辅助栈栈顶 -3。 ✅ |
pop() |
[-2, 0] | [-2] | 弹出主栈顶 -3，它等于辅助栈顶 -3，所以辅助栈也弹出。 |
top() |
[-2, 0] | [-2] | 返回主栈顶 0。 ✅ |
getMin() |
[-2, 0] | [-2] | 返回辅助栈栈顶 -2。 ✅ |
可以看到，通过辅助栈，我们完美地在 O(1) 时间内完成了所有操作。
第四步：代码实现（Python）
下面是基于上述“辅助栈”思路的 Python 代码实现，非常清晰。
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = [] # 主栈
self.min_stack = [] # 辅助栈，用于存储各个状态的最小值
def push(self, val: int) -> None:
# 元素总是压入主栈
self.stack.append(val)
# 如果辅助栈为空，或者新值 <= 当前最小值，则压入辅助栈
# 注意：这里用 <= 是为了处理重复最小值的情况
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
# 弹出主栈栈顶元素
popped_value = self.stack.pop()
# 如果弹出的元素正好等于当前最小值，则辅助栈也要弹出
if popped_value == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
# 返回主栈栈顶元素
return self.stack[-1]
def getMin(self) -> int:
# 返回辅助栈栈顶元素，即当前最小值
return self.min_stack[-1]
# 测试代码，对应上面的示例
# minStack = MinStack()
# minStack.push(-2)
# minStack.push(0)
# minStack.push(-3)
# print(minStack.getMin()) # -> -3
# minStack.pop()
# print(minStack.top()) # -> 0
# print(minStack.getMin()) # -> -2
第五步：总结与要点回顾
- 核心思想：空间换时间。用一个额外的栈（辅助栈）来存储历史最小值信息，从而保证在
pop操作后能立即知道新的最小值。 - 关键细节：
push时的判断条件：是val <= getMin()，而不是<。这是为了正确处理重复的最小值。pop时的同步：只有当主栈弹出的值 等于 当前最小值时，辅助栈才弹出。
- 时间复杂度：所有操作
push、pop、top、getMin的时间复杂度均为O(1)。 - 空间复杂度：
O(n)，其中n为操作总数，最坏情况下所有元素都会被压入辅助栈。
这道题很好地考察了对栈数据结构的理解以及如何通过组合简单数据结构来解决复杂问题。希望这个循序渐进的讲解能让你完全掌握它！