【每日算法】LeetCode 155. 最小栈-编程实验室

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 155. 最小栈

1. 题目描述

1.1 原题链接与基本信息

题目链接：LeetCode 155. 最小栈
难度：简单
标签：栈、设计

1.2 题目描述与示例

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

实现MinStack类:

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

示例 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^31 <= val <= 2^31 - 1
pop、top和getMin操作总是在非空栈上调用。
最多调用3 * 10^4次push、pop、top和getMin。

2. 问题分析

2.1 问题核心

我们需要实现一个特殊的栈，它除了支持常规的栈操作（push、pop、top）外，还需要支持在常数时间内返回当前栈中的最小元素。

2.2 难点分析

常规的栈结构可以在常数时间内完成push、pop、top操作，但是要获取最小值，通常需要遍历整个栈，时间复杂度为 O(n)，不符合题目要求。因此，我们需要在数据结构和算法上进行设计，使得getMin操作的时间复杂度为 O(1)。

3. 解题思路

3.1 思路一：辅助栈法（最优解）

使用两个栈：一个主栈用于存储所有元素，另一个辅助栈用于存储主栈每个状态下的最小值。当元素入栈时，主栈正常压入，辅助栈则压入当前主栈的最小值（即辅助栈栈顶和当前值中的较小者）。出栈时，两个栈同时弹出栈顶元素。这样，辅助栈的栈顶始终对应主栈当前状态的最小值。

3.2 思路二：单个栈存储差值法

只使用一个栈，存储每个元素与当前最小值的差值。同时用一个变量min记录当前最小值。入栈时，压入差值并更新最小值；出栈时，根据栈顶差值反向更新最小值。这种方法节省了空间，但实现稍复杂，且需要注意整数溢出问题（JavaScript 使用 Number 类型，安全整数范围为-2^53 ~ 2^53，题目值范围在 32 位整数内，因此安全）。

3.3 思路三：节点存储当前最小值法

定义一个节点结构，每个节点存储当前值以及到该节点为止的最小值。这样，栈中每个元素都携带了当前状态的最小值信息。出栈操作不影响其他节点的最小值。这种方法同样可以实现常数时间获取最小值，但每个节点需要额外存储一个最小值，空间复杂度为 O(n)。

4. 代码实现

4.1 辅助栈法（JavaScript实现）

classMinStack{constructor(){this.stack=[];this.minStack=[];// 辅助栈，与主栈同步操作，栈顶存储当前主栈中的最小值}push(val){this.stack.push(val);// 如果辅助栈为空，或者当前值小于等于辅助栈栈顶，则压入当前值；否则重复压入辅助栈栈顶if(this.minStack.length===0||val<=this.minStack[this.minStack.length-1]){this.minStack.push(val);}else{this.minStack.push(this.minStack[this.minStack.length-1]);}}pop(){if(this.stack.length===0)return;this.stack.pop();this.minStack.pop();}top(){returnthis.stack[this.stack.length-1];}getMin(){returnthis.minStack[this.minStack.length-1];}}

4.2 差值法（JavaScript实现）

classMinStack{constructor(){this.stack=[];this.min=Infinity;// 当前最小值}push(val){if(this.stack.length===0){this.stack.push(0);// 差值为0this.min=val;}else{constdiff=val-this.min;this.stack.push(diff);// 如果差值小于0，说明val比当前最小值还小，更新最小值if(diff<0){this.min=val;}}}pop(){if(this.stack.length===0)return;constdiff=this.stack.pop();// 如果差值小于0，说明当前栈顶元素就是最小值，出栈后需要恢复前一个最小值if(diff<0){this.min=this.min-diff;// 因为 diff = val - oldMin, 且 val 就是当前的 min，所以 oldMin = min - diff}// 如果栈为空，重置minif(this.stack.length===0){this.min=Infinity;}}top(){constdiff=this.stack[this.stack.length-1];// 如果差值大于等于0，说明当前栈顶元素不是最小值，真实值为 min + diff// 如果差值小于0，说明当前栈顶元素是最小值，真实值就是 minreturndiff>=0?this.min+diff:this.min;}getMin(){returnthis.min;}}

4.3 节点存储法（JavaScript实现）

classMinStack{constructor(){this.stack=[];// 栈中每个元素是一个对象，包含val和当前最小值}push(val){if(this.stack.length===0){this.stack.push({val,min:val});}else{constcurrentMin=this.stack[this.stack.length-1].min;this.stack.push({val,min:Math.min(currentMin,val)});}}pop(){this.stack.pop();}top(){returnthis.stack[this.stack.length-1].val;}getMin(){returnthis.stack[this.stack.length-1].min;}}

5. 复杂度与优缺点对比

5.1 复杂度分析

方法	时间复杂度 (push/pop/top/getMin)	空间复杂度
辅助栈法	O(1)	O(n)
差值法	O(1)	O(n) (最坏情况下与辅助栈法相同，但平均情况下节省空间)
节点存储法	O(1)	O(n)

5.2 优缺点对比表格

方法	优点	缺点
辅助栈法	思路直观，易于理解和实现；操作同步，逻辑简单。	需要额外的栈，最坏情况下空间加倍。
差值法	只使用一个栈，节省了空间（尤其当元素较多且最小值变化不大时）。	实现稍复杂，需要考虑整数溢出（在JavaScript中问题不大）；存储差值可能带来精度问题（但题目为整数，所以安全）。
节点存储法	每个节点独立存储最小值，逻辑清晰；不需要额外数据结构。	每个节点需要额外存储一个最小值，空间开销与辅助栈法类似。

最优解建议：辅助栈法。因其实现简单，可读性强，在大多数情况下是首选。虽然空间复杂度为 O(n)，但实际应用中通常可以接受。