从一道面试题看算法思维：最小栈（Min Stack）的从 O(N) 到 O(1) 进化之路-洪萨配资

“最小栈”（LeetCode 155题）作为一道非常经典的试金石。它不涉及复杂的动态规划或图论，却能精准地考察候选人对数据结构的理解深度以及空间换时间这一核心算法思想的掌握程度。
题目要求看似简单：设计一个栈，支持 push、pop、top 操作，并能在常数时间

O(1)

内检索到最小元素 getMin。
很多候选人在看到题目时，往往忽略了

O(1)

这个关键约束，直接给出了一个功能正确但性能不达标的方案。今天，我们就从面试官的视角，来剖析这道题从

O(N)

到

O(1)

的进化过程。
第一阶段：直觉与妥协 (暴力解法)
当被问到“如何实现一个支持获取最小值的栈”时，大多数人的第一直觉是利用 JavaScript 数组的原生方法。既然栈的本质是先进后出（LIFO），那么 push、pop 和 top 都很容易实现。
对于 getMin，最朴素的想法是：既然我要找最小值，那就遍历整个数组好了。
以下是这类回答的典型代码实现：
JavaScript

// ES5 构造函数 const MiniStack = function() { this.stack = []; // 存储数据的数组 } MiniStack.prototype.push = function(x) { this.stack.push(x); } MiniStack.prototype.pop = function() { return this.stack.pop(); } MiniStack.prototype.top = function() { if(!this.stack || !this.stack.length){ return; } return this.stack[this.stack.length-1]; } // 暴力解法核心：遍历查找 O(N) MiniStack.prototype.getMin = function() { let minValue = Infinity; // 初始化为无穷大 const { stack } = this; // 遍历整个栈寻找最小值 for(let i = 0; i < stack.length; i++){ if(stack[i] < minValue){ minValue = stack[i]; } } return minValue; }

面试官点评
这份代码从功能上来说是正确的。它利用了 JS 数组模拟栈，push、pop、top 的时间复杂度确实是

O(1)

。
但是，getMin 方法的实现存在致命弱点：它的时间复杂度是

O(N)

。
随着栈内元素数量（N）的增加，获取最小值的耗时将线性增长。如果在高频调用的场景下，这种遍历操作是不可接受的性能瓶颈。在面试中，这只能算是一个“勉强及格”的答案，因为它没有体现出任何算法优化的思维。
第二阶段：思维跃迁 (空间换时间)
如何将

O(N)

优化为

O(1)

？这需要我们转换思维。
在暴力解法中，我们每次调用 getMin 都要重新计算。也就是我们“忘记”了之前的比较结果。如果我们能有一种机制，能够“记住”随着数据入栈过程中，每一个状态下的最小值，那就不需要回头遍历了。
这里引入算法设计中极重要的思想：空间换时间。
我们需要引入一个辅助栈（Auxiliary Stack）。

数据栈 (stack)：负责常规的数据存储，维持栈的正常逻辑。
辅助栈 (stack2)：负责同步存储当前数据栈对应的最小值。

核心策略：辅助栈的栈顶，永远存储着当前数据栈中所有元素的最小值。这实际上维护了一个非严格单调递减的序列。
第三阶段：完美实现 (双栈协同)
有了辅助栈的思路，接下来的难点在于：如何保持两个栈的状态同步？
我们需要处理好两个关键逻辑：

入栈 (Push)：新元素进来了，辅助栈存不存？
出栈 (Pop)：数据栈弹出了，辅助栈要不要跟着弹？

以下是经过逻辑修正后的

O(1)

完美实现：
JavaScript

const MiniStack = function() { this.stack = []; // 数据栈 this.stack2 = []; // 辅助栈（单调栈，栈顶即为最小值） } // O(1) MiniStack.prototype.push = function(x) { // 1. 数据栈必须入栈 this.stack.push(x); // 2. 辅助栈入栈逻辑 // 如果辅助栈为空，或者新元素 x 小于等于 辅助栈栈顶，则入辅助栈 // 注意：这里必须是 <=，不能只是 <，否则会有重复最小值丢失的问题 if(this.stack2.length === 0 || x <= this.stack2[this.stack2.length-1]) { this.stack2.push(x); } } // O(1) MiniStack.prototype.pop = function() { // 1. 数据栈弹出 const val = this.stack.pop(); // 2. 辅助栈同步逻辑 // 如果弹出的元素等于辅助栈栈顶元素，说明最小值被移除，辅助栈也要弹出 if(val === this.stack2[this.stack2.length-1]) { this.stack2.pop(); } return val; } // O(1) MiniStack.prototype.top = function() { return this.stack[this.stack.length-1]; } // O(1) MiniStack.prototype.getMin = function() { // 直接返回辅助栈栈顶，无需遍历 return this.stack2[this.stack2.length-1]; }

深度解析
1. Push 操作的去重与同步
在 push 方法中，判断条件 x <= this.stack2[top] 至关重要。

为什么要判断大小？我们只关心比当前最小值更小（或相等）的数。如果新来的数比当前最小值还大，它绝不可能是当前的最小值，因此不需要压入辅助栈。这保证了辅助栈的单调递减特性。
为什么要包含等于（<=）？这是一个常见的坑。假设入栈序列为 [5, 2, 2]。
- 如果不包含等于：辅助栈通过判断只存入第一个 2。
- 当数据栈弹出最上面的 2 时，代码会误以为最小值被移除了，导致辅助栈唯一的 2 也被弹出。
- 此时数据栈里还剩一个 2，但辅助栈里的最小值变成了 5。这就产生了 Bug。
- 因此，重复的最小值必须同时压入辅助栈。

2. Pop 操作的同步
在 pop 方法中，我们对比数据栈弹出的值与辅助栈栈顶的值。
只有当两者相等时，才弹出辅助栈。这意味着：我们移除的正是当前的最小值。辅助栈弹出后，新的栈顶自然就变成了“次小值”（即之前的最小值），完美还原了历史状态。
3. GetMin 的极致性能
由于辅助栈的精心维护，其栈顶永远是全局最小值。getMin 变成了简单的数组索引访问，没有任何循环，时间复杂度稳稳落在 O(1)
总结：
辅助栈就像是数据栈的“历史快照”索引。无论数据栈怎么进出，辅助栈的栈顶始终指向“当前存活数据中的最小者”。这种设计将 getMin 的复杂度从线性阶降维到了常数阶。在实际面试中，写出代码往往只占 60% 的分数。剩下的 40% 取决于你能否清晰地解释“为什么引入辅助栈”、“如何处理重复最小值”以及“空间与时间的权衡”。算法不仅仅是背诵代码，更是对数据流动和资源消耗的精准控制。
如果这篇文章对你有帮助的话，就请你点个赞吧！！！