题目回顾

设计一个支持push、pop、top 操作，并能在常数时间 O(1) 内检索最小元素的栈。

实现MinStack类：

• MinStack()初始化栈

• void push(int val)将元素 val 推入栈

• void pop()删除栈顶元素

• int top()获取栈顶元素

• int getMin()获取栈中最小元素

示例：

输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2]

解题思路

核心问题

普通栈无法在O(1)时间获取最小值，因为pop()可能改变栈中最小值。

解决方法：使用辅助栈（双栈法）

双栈法

维护两个栈：

操作规则：

1. push(val)

   • data 栈正常入栈

   • min 栈入栈min(val, minStk.top())（保证栈顶永远是最小值）

2. pop()

   • data 栈 pop

   • min 栈 pop

3. top()

   • 返回 data 栈顶

4. getMin()

   • 返回 min 栈顶

动态演示

操作: push(-2) data: [-2] min : [-2] 操作: push(0) data: [-2,0] min : [-2,-2] 操作: push(-3) data: [-2,0,-3] min : [-2,-2,-3] getMin() -> -3 pop() data: [-2,0] min : [-2,-2] getMin() -> -2

C++ 实现

#include <stack> using namespace std; class MinStack { private: stack<int> data; stack<int> minStk; public: MinStack() { } void push(int val) { data.push(val); if (minStk.empty()) minStk.push(val); else minStk.push(min(val, minStk.top())); } void pop() { data.pop(); minStk.pop(); } int top() { return data.top(); } int getMin() { return minStk.top(); } };

优化思路（可选）

1. 单栈+差值法：

   • 只用一个栈，通过存储val - min差值来记录历史最小值

   • 优点：节省空间

   • 缺点：逻辑复杂，不易理解

2. 面试时推荐：

   • 实现双栈法，稳、易懂

   • 口头提及单栈法，显示你掌握高级技巧

复杂度分析

✅总结：

• 双栈法是最直观、面试最稳的方案

• min 栈保证了 O(1) 时间取最小值

• 逻辑清晰，代码简洁