引言
欢迎来到本系列具有里程碑意义的第十篇！今天，我们将继续探索“栈”这种数据结构的魅力，但这次，我们要挑战一个“带增强功能”的特殊栈设计问题——LeetCode 155. 最小栈。
这道题要求我们实现一个除了常规 push, pop, top 功能外，还能在常数时间 O(1) 内检索到当前栈中最小元素的 MinStack。
这道题是考察数据结构设计能力的经典题目。它迫使我们思考一个深刻的问题：如何在遵循栈“后进先出”规则的同时，高效地维护一个全局的“最值”信息？
本文将带你一起：
探讨一个直观但存在缺陷的思路：只用一个变量来记录最小值。
通过一个思想实验，揭示上述思路为何会在 pop 操作时“失忆”。
深入理解辅助栈思想的精髓，看它如何像“历史快照”一样，完美地解决了问题。
一、题目呈现
题目编号：155. 最小栈
题目难度：中等
题目描述：
设计一个支持 push ，pop ，top 和 getMin 操作的最小栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
每个函数都必须在 O(1) 的时间复杂度内完成。
示例：
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
二、我的思考：一个变量存最小值的“陷阱”
（这里采用你的笔记思路）
看到 getMin 的要求，我的第一反应是：这很简单，我只需要一个普通的栈来存储数据，再用一个额外的变量，比如 min_val，来实时记录全局的最小值就可以了。
push(x) 时：我将 x 正常压入数据栈，然后 min_val = min(min_val, x)。
getMin() 时：直接返回 min_val。
这个思路看起来很完美，时间复杂度都是 O(1)。但是，pop() 操作怎么办？
这个思路的致命缺陷：
让我们进行一次思想实验。
push(5): 数据栈 [5], min_val = 5。
push(3): 数据栈 [5, 3], min_val = 3。
pop(): 数据栈弹出 3，变为 [5]。问题来了：我们刚刚弹出的 3 正是当前的最小值。那么，新的 min_val 应该是多少？应该是 5。但是，我们的 min_val 变量只记得“历史最低是3”，它完全丢失了“次小值是多少”这个历史信息。它无法回溯！
结论：只用一个变量的方案，在 pop 操作面前会“失忆”，无法满足要求。我们需要一种能够记录“历史状态”的机制。
三、豁然开朗：辅助栈的“历史快照”模型
为了解决“失忆”问题，我们引入一个辅助栈 (min_stack)。它的使命，就是为主数据栈的每一个状态，都同步地保存一个“历史快照”，记录下“当数据栈是这个样子时，当前的最小值是多少”。
核心思想：
我们维护两个栈：一个数据栈 (data_stack)，一个辅助栈 (min_stack)。
这两个栈必须严格保持同步：任何时候，它们的高度（元素数量）都必须完全相同。
push 操作时：
data_stack 正常压入新元素 val。
min_stack 压入 min(val, 当前的最小值)。
pop 操作时：
data_stack 和 min_stack 同时弹出栈顶元素。
getMin 操作时：
我们根本不需要看 data_stack，只需要直接返回 min_stack 的栈顶元素即可。
这个 min_stack 就像是 data_stack 的一个“伴侣”，min_stack 的第 i 个元素，就记录了当 data_stack 有 i 个元素时的全局最小值。
C++ 代码实现 (辅助栈法)
#include <stack>
#include <algorithm> // 为了使用 std::min
#include <climits> // 为了使用 INT_MAX
class MinStack {
// 1.
private:
std::stack<int> data_stack;
std::stack<int> min_stack;
public:
MinStack() {
// 2.
min_stack.push(INT_MAX);
}
void push(int val) {
// 3.
data_stack.push(val);
// 4.
min_stack.push(std::min(min_stack.top(), val));
}
void pop() {
// 5.
data_stack.pop();
min_stack.pop();
}
int top() {
return data_stack.top();
}
int getMin() {
// 6.
return min_stack.top();
}
};代码逐点解释
private: ...: 我们将两个栈作为私有成员，这是良好的封装实践，防止外部代码直接篡改。
min_stack.push(INT_MAX);: 哨兵技巧。我们在构造函数中就向 min_stack 推入一个“无限大”的值。这巧妙地消除了“第一次 push 时 min_stack 为空”的边界情况，让 push 的逻辑更统一。
data_stack.push(val);: 数据栈的行为和普通栈完全一样。
min_stack.push(std::min(min_stack.top(), val));: 这是辅助栈的核心逻辑。每次 push，我们都将“新来的值 val”和“之前的最小值 min_stack.top()”中的较小者，作为新的“当前最小值”压入辅助栈。
pop(): 同步弹出。这是维持两个栈状态一致的关键。data_stack 弹出一个元素，min_stack 也必须弹出一个对应的“历史快照”。
getMin(): O(1) 的魔法。我们不需要做任何计算，直接返回 min_stack 的栈顶元素，它永远记录着当前状态的正确最小值。
四、总结与收获
复杂度分析：所有操作（push, pop, top, getMin）的时间复杂度都为 O(1)。我们使用了一个额外的栈，因此空间复杂度为 O(n)。
核心思想：辅助栈是一种经典的“用空间换时间”的策略。它通过同步地记录主数据结构的每一个历史状态下的某个特定值（本题中是最小值），来将查询该特定值的操作优化到 O(1) 的时间复杂度。
关键技巧：同步 push/pop 是保证辅助栈与主数据栈状态一致的根本。哨兵节点/值（如本题的 INT_MAX 或链表的 dummy 节点）是消除边界情况、简化代码逻辑的强大技巧。