.jpg)
625 字
3 分钟
最小栈
.jpg)
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
解题思路
- 辅助栈同步法：
- 主栈正常存储元素
- 辅助栈实时存储当前栈内最小值
push时更新辅助栈：min_stack.push(min(val, min_stack.top()))
- 差值存储法：
- 单栈存储当前元素与历史最小值的差值
- 用变量
min_val追踪当前最小值 push/pop时通过差值反推原始值与更新min_val
关键洞察
- 最小值传递性：新元素入栈时，最小值只可能不变或更新为新值
- 状态同步原理：辅助栈与主栈高度始终同步，确保每个操作对应正确的最小值
- 空间优化本质：差值法将空间降到O(1)，但需处理整数溢出问题
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 辅助栈法 | O(1) | O(n) |
| 差值法 | O(1) | O(1) |
代码实现
最小栈辅助法
// @link {https://leetcode.cn/problems/min-stack/}
var MinStack = function () { this.stack = []; this.minStack = [];};
/** * @param {number} val * @return {void} */MinStack.prototype.push = function (val) { this.stack.push(val); if ( this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1] ) { this.minStack.push(val); }};
/** * @return {void} */MinStack.prototype.pop = function () { if (this.stack.pop() === this.minStack[this.minStack.length - 1]) { this.minStack.pop(); }};
/** * @return {number} */MinStack.prototype.top = function () { return this.stack[this.stack.length - 1];};
/** * @return {number} */MinStack.prototype.getMin = function () { return this.minStack[this.minStack.length - 1];};差值法
class MinStack { constructor() { this.stack = []; // 存储与最小值的差值 this.minVal; // 当前最小值 } push(val) { if (this.stack.length === 0) { // 栈为空时，初始化最小值并压入0（表示无差值） this.minVal = val; this.stack.push(0); } else { // 计算当前值与当前最小值的差值 const diff = val - this.minVal; this.stack.push(diff); // 如果差值小于0，说明新值更小，更新最小值 if (diff < 0) { this.minVal = val; } } } pop() { if (this.stack.length === 0) return; const diff = this.stack.pop(); // 如果弹出的是负数，需要恢复前一个最小值 if (diff < 0) { this.minVal = this.minVal - diff; // 恢复公式：minVal = minVal - diff } } top() { const diff = this.stack[this.stack.length - 1]; // 根据差值类型计算实际值 return diff >= 0 ? this.minVal + diff // 非最小值元素 : this.minVal; // 当前最小值元素 } getMin() { return this.minVal; }}