企业官网建设流程全解析

LeetCode 155 最小栈（Min Stack）题解：双栈与差值单栈两种常数时间取最小设计

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文基于本仓库 problems/155.min-stack.en.md（中文对照版见 problems/155.min-stack.md），系统讲解 LeetCode 155「最小栈」这道经典设计题：如何在支持 push、pop、top 常规栈操作的同时，用O(1) 时间复杂度随时取出栈内最小元素。文章完整继承原文档的题目要求、双栈解法与差值单栈解法，并补齐 JS / C++ / Java / Python 四种语言的完整可运行代码与推导过程；读完你既能掌握两种主流设计方案及其 trade-off，也能理解它们在本仓库设计题体系中的位置（参见 thinkings/design.md 中对本题"简单"难度与设计思路的分类）。

题目描述

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

• push(x)—— 将元素 x 推入栈中；
• pop()—— 删除栈顶的元素；
• top()—— 获取栈顶元素；
• getMin()—— 检索栈中的最小元素。

示例：

输入： ["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.

提示：pop、top和getMin操作总是在非空栈上调用。

说明：仓库示例代码中 JS / Python 版本将取最小值方法命名为min()（如var param_4 = obj.min()），LeetCode 平台接口名通常为getMin()，实际提交时以平台约定的方法名为准，两者逻辑完全一致。

前置知识：栈（LIFO）

本题的基础数据结构是栈。在本仓库 thinkings/basic-data-structure.md 中，栈被定义为一种受限的序列——无论入栈还是出栈，都只能在栈顶（末尾）操作：

• push：添加元素到栈的顶端（末尾）；
• pop：移除栈最顶端（末尾）的元素；
• peek/top：只返回不弹出栈顶元素。

以上操作可概括为后进先出（LIFO, Last In First Out）。最小栈的难点正在于：普通栈只能看到栈顶，要额外维护"任意时刻全栈最小值"且保证 O(1) 查询，就必须在 push/pop 时同步维护最小信息。

方法一：双栈（辅助最小栈）

思路

使用两个栈：

• 数据栈（stack / data）：存放全部元素，push、pop都是对它的正常操作；
• 最小栈（minStack / helper）：只存放"当前出现过的最小值序列"。

操作规则：

1. push(x)：数据栈正常入栈；同时判断——若最小栈为空，或x <= 最小栈栈顶，则把 x 也压入最小栈（相等也要压入，原因见下）；
2. pop()：数据栈正常出栈；同时判断——若弹出的元素与最小栈栈顶相同，则最小栈栈顶也一并弹出；
3. top()：直接返回数据栈栈顶；
4. getMin() / min()：直接返回最小栈栈顶。

关键点

• 往最小栈 push 的判断条件应为：栈为空，或x小于等于最小栈栈顶元素。注意是<=而非<，否则当出现多个相等的最小值时，后续 pop 会把唯一记录的最小值弹掉，导致最小值丢失；
• pop 时用"弹出值是否等于最小栈栈顶"来判断是否需要同步弹出，因此必须保证相等值时都被记录。

代码

JavaScript

/** * initialize your data structure here. */ var MinStack = function () { this.stack = []; this.minStack = []; }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function (x) { this.stack.push(x); if (this.minStack.length == 0 || x <= this.minStack[this.minStack.length - 1]) { this.minStack.push(x); } }; /** * @return {void} */ MinStack.prototype.pop = function () { const x = this.stack.pop(); if (x !== void 0 && x === 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.min = function () { return this.minStack[this.minStack.length - 1]; }; /** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(x) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.min() */

C++

class MinStack { stack<int> data; stack<int> helper; public: /** initialize your data structure here. */ MinStack() {} void push(int x) { data.push(x); if (helper.empty() || helper.top() >= x) { helper.push(x); } } void pop() { int top = data.top(); data.pop(); if (top == helper.top()) { helper.pop(); } } int top() { return data.top(); } int getMin() { return helper.top(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */

Java

public class MinStack { // 数据栈 private Stack<Integer> data; // 辅助栈 private Stack<Integer> helper; /** initialize your data structure here. */ public MinStack() { data = new Stack<>(); helper = new Stack<>(); } public void push(int x) { // 辅助栈在必要的时候才增加 data.add(x); if (helper.isEmpty() || helper.peek() >= x) { helper.add(x); } } public void pop() { // 关键：data 一定得 pop() if (!data.isEmpty()) { // 注意：声明成 int 类型，这里完成了自动拆箱，从 Integer 转成了 int， // 因此下面的比较可以使用 "==" 运算符 int top = data.pop(); if (top == helper.peek()) { helper.pop(); } } } public int top() { if (!data.isEmpty()) { return data.peek(); } return -1; } public int getMin() { if (!helper.isEmpty()) { return helper.peek(); } return -1; } }

Python3

class MinStack: def __init__(self): """ initialize your data structure here. """ self.stack = [] self.minstack = [] def push(self, x: int) -> None: self.stack.append(x) if not self.minstack or x <= self.minstack[-1]: self.minstack.append(x) def pop(self) -> None: tmp = self.stack.pop() if tmp == self.minstack[-1]: self.minstack.pop() def top(self) -> int: return self.stack[-1] def min(self) -> int: return self.minstack[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.min()

说明：题目提示保证pop、top、getMin均在非空栈上调用，因此上述 Java 实现中空栈分支的返回值在实际评测中不会被触发。

复杂度分析

• 时间复杂度：O(1) —— push、pop、top、getMin 均只做常数次栈顶操作；
• 空间复杂度：数据栈本身 O(n)；辅助最小栈在最坏情况下（元素单调不增时每个元素都入辅助栈）也为 O(n)，即额外空间 O(n)。

方法二：单栈 + 差值存储（O(1) 额外空间）

思路

符合直觉的做法是：每次对栈进行修改（push / pop）时都重新遍历计算最小值，getMin直接返回该值——但这样每次修改的代价是 O(n)。

本方法的核心改进是：栈里存的不再是真实值，而是真实值与"上一个最小值"的差。同时用单个变量minV维护当前最小值。具体来说：

• push(x)：入栈x - minV（此处minV是 x 入栈之前的当前最小值，即"上一个最小值"），若x < minV则更新minV = x；
• pop()：取出栈顶差值tmp，若tmp < 0，说明被弹出的正是当前最小值，需恢复上一个最小值：minV = minV - tmp；
• top()：根据栈顶差值tmp还原真实值：若tmp < 0则真实值就是minV（此时栈顶即最小值），否则真实值= tmp + minV；
• getMin() / min()：直接返回minV。

为什么栈顶差值小于 0 时，弹出/查询到的就是最小值？推导如下：入栈时记录的是栈顶元素 = 真实值 - 上一个最小值；而"真实值是当前最小值"意味着真实值 < 上一个最小值，因此真实值 - 上一个最小值 < 0。反过来，当tmp < 0时必然有"真实值 = min"，于是上一个最小值= min - tmp。

关键点

• 最小栈存储的不是真实值，而是真实值与min的差值；
• top还原数据时，千万注意用的是"上一个"最小值（即元素入栈那一刻之前的minV），而不是"当前"最小值；
• 用long（C++ / Java）存储差值，避免x - min溢出风险。

图解演示

下面的图解来自本仓库 assets/problems/155.min-stack-1.png，展示了差值法维护最小值的初始状态与 min 指针：

出栈时按差值正负分两种情况处理（图见 assets/problems/155.min-stack-2.png 与 assets/problems/155.min-stack-3.png）：

• 弹出的栈顶差值tmp < 0：说明被弹出的是当前最小值，需要更新minV（上一个最小值 =minV - tmp）；
• 弹出的栈顶差值tmp > 0：说明它对最小值"没有影响"，minV保持不变。

代码

JavaScript

/* * @lc app=leetcode id=155 lang=javascript * * [155] Min Stack */ /** * initialize your data structure here. */ var MinStack = function () { this.stack = []; this.minV = Number.MAX_VALUE; }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function (x) { // update 'min' const minV = this.minV; if (x < this.minV) { this.minV = x; } return this.stack.push(x - minV); }; /** * @return {void} */ MinStack.prototype.pop = function () { const item = this.stack.pop(); const minV = this.minV; if (item < 0) { this.minV = minV - item; return minV; } return item + minV; }; /** * @return {number} */ MinStack.prototype.top = function () { const item = this.stack[this.stack.length - 1]; const minV = this.minV; if (item < 0) { return minV; } return item + minV; }; /** * @return {number} */ MinStack.prototype.min = function () { return this.minV; }; /** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(x) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.min() */

C++

class MinStack { stack<long> data; long min = INT_MAX; public: /** initialize your data structure here. */ MinStack() {} void push(int x) { data.push(x - min); if (x < min) { min = x; } } void pop() { long top = data.top(); data.pop(); // 更新最小值 if (top < 0) { min -= top; } } int top() { long top = data.top(); // 最小值为 min if (top < 0) { return min; } else { return min + top; } } int getMin() { return min; } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */

Java

class MinStack { long min; Stack<Long> stack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<>(); } public void push(int x) { if (stack.isEmpty()) { stack.push(0L); min = x; } else { stack.push(x - min); if (x < min) min = x; } } public void pop() { long p = stack.pop(); if (p < 0) { // if (p < 0), the popped value is the min // Recall p is added by this statement: stack.push(x - min); // So, p = x - old_min // old_min = x - p // again, if (p < 0), x is the min so: // old_min = min - p min = min - p; } } public int top() { long p = stack.peek(); if (p < 0) { return (int) min; } else { // p = x - min // x = p + min return (int) (p + min); } } public int getMin() { return (int) min; } }

Python

class MinStack: def __init__(self): """ initialize your data structure here. """ self.minV = float('inf') self.stack = [] def push(self, x: int) -> None: self.stack.append(x - self.minV) if x < self.minV: self.minV = x def pop(self) -> None: if not self.stack: return tmp = self.stack.pop() if tmp < 0: self.minV -= tmp def top(self) -> int: if not self.stack: return tmp = self.stack[-1] if tmp < 0: return self.minV else: return self.minV + tmp def min(self) -> int: return self.minV # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.min()

复杂度分析

• 时间复杂度：O(1) —— 四种操作均只涉及常数次算术与栈顶访问；
• 空间复杂度：额外空间 O(1)（仅一个min变量），数据栈本身 O(n)。相比双栈方案，差值法把辅助空间从最坏 O(n) 压到了 O(1)，代价是代码可读性稍差、需要小心处理差值恢复逻辑。

两种方案对比与仓库扩展阅读

两套实现均可在仓库中找到完整源码：中文/英文题解见 problems/155.min-stack.md 与 problems/155.min-stack.en.md，对应的过程图解源文件为 assets/drawio/155.min-stack.drawio。

如果你想在同类设计题上继续巩固这套"在标准数据结构上附加一个同步维护的辅助信息"的套路，本仓库还提供了系列题目可对比学习：

• 232.implement-queue-using-stacks：用两个栈实现队列，同样属于"双结构协作"的经典设计；
• 895.maximum-frequency-stack：在栈基础上要求 O(1) 弹出"出现频率最高"的元素，是最小栈思路的进阶版；
• 更多设计题分类与难度定位可参考 thinkings/design.md，本题被归入简单档的设计题代表。

总结

LeetCode 155 最小栈考察的是对"栈只能访问栈顶"这一约束的突破：通过双栈同步维护最小值历史，或单栈差值存储 + 单个 min 变量，都能把getMin从 O(n) 降到 O(1)。双栈方案更直观，适合面试时优先给出；差值方案空间更优，适合在明确提示优化空间时展开推导。无论哪种方案，把握住"push 用上一个最小值、pop 用差值符号判断是否更新最小值"这两个要点，就能一次写对。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode