企业官网建设流程全解析

做力扣hot100有一阵子了，第155题“最小栈”可以说是我印象最深的一道简单题。说它简单，因为代码量确实不大，核心解法几行就能写完；说它印象深，是因为这题几乎每次刷都有新体会，而且面试里出现频率极高，它考察的不是“会不会用栈”，而是“在特定约束下怎么重新设计一个数据结构”。今天就把这题的两个主流解法、完整推导过程、我踩过的坑、以及面试官可能会追问的东西一次讲清楚。如果你正在刷hot100，或者准备面试想快速过一遍高频题，这篇可以直接参考。

很多人看到题目第一反应是：维护一个变量记住最小值不就完了？真这么简单，它就不会出现在hot100里了。最小栈真正的难点在于，你不仅要能快速拿到当前栈的最小值，还要在pop之后，让最小值“自动回退”到上一个状态。这就意味着，单一变量是不够的，你需要设计一套机制，把最小值的变化历史存下来。这题的两个经典解法，本质上是两种不同的“历史记录”策略：一种用额外栈存历史，一种把历史编码进栈元素本身。下面我按思考的递进顺序，把这两个方案完整拆开讲一遍。

1. 题目到底在考什么：核心需求与思路拆解

1.1 最小栈题面速读与真实考点

先看题目要求：设计一个支持push、pop、top、getMin四个操作，并且能在常数时间O(1)内返回最小值的栈。这题在力扣上的难度标的是“中等”，但它经常和各种简单栈题放在一起讨论，原因就是它考察的不是某个API的用法，而是“数据结构设计”的思维。

push、pop、top这三个操作，用系统自带的栈就能做到O(1)，关键是getMin怎么在O(1)内返回当前栈中的最小值。最常见的暴力做法是：调用getMin时遍历一遍整个栈，找出最小值再返回，时间复杂度是O(n)。题目明确要求O(1)，这就在告诉你：必须用空间换时间，在数据进入栈的同时，把最小值的变化信息记录下来。

这里有个很容易被忽略的细节：栈的特点是“后进先出”，所以你不仅要维护“当前最小值”，还要能在弹出元素后，恢复到“弹出之前的最小值”。这个“可回退”的需求，是这题区别于普通“找最值”问题的关键，也是设计辅助结构时的核心约束。

1.2 为什么不能只用一个变量记住最小值

假设我们用一个min变量，每次 push 时更新它。比如依次 push 3、5、2、1，min分别为 3、3、2、1，看起来很顺利。但接下来连续执行两次 pop 操作：

• 第一次 pop，弹出的是 1，也就是当前最小值，此时栈里还剩 3、5、2，正确的最小值应该变成 2；
• 可问题是，min变量已经被赋值为 1，弹出 1 之后，它并不知道上一个最小值是 2，而且也没有任何途径能找回这个信息。

这就是单一变量方案的核心缺陷：它只记录了“当前结果”，没有记录“结果的历史变化轨迹”。一旦最小值对应的元素被弹出，历史信息就断了。用一个简单比喻：这就好比登山的时候只记最高海拔，但下山时不记得曾经到过哪个垭口，自然无法回退到上一个高峰的海拔。

所以要解决这个问题，思路就很清晰了：必须把最小值的历史变化过程保存下来。最简单的做法，就是再开一个栈，专门记录“到目前为止的最小值”，这就是下面要讲的辅助栈方案。

1.3 O(1)复杂度的本质：数据结构和算法的配合

做题的时候最容易忽略的是“为什么辅助栈能保证 O(1)”。很多人只是记住了代码，却说不清原理。这里的关键在于：辅助栈的栈顶，永远维护着“主栈当前状态下的最小值”。

也就是说，辅助栈的高度和主栈保持一致（或者保持一致的状态映射），主栈 push 一个元素进栈时，辅助栈同步记录“当前全局最小值”；主栈 pop 时，辅助栈也跟着 pop。这样，任何时刻getMin都只需要读取辅助栈的栈顶元素，而栈顶操作本身就是O(1)，整个过程完全不依赖栈里有多少个元素。

从工程角度看，这就是典型的“缓存思想”——用一个额外的数据结构，把需要频繁查询的结果提前维护好，查询时直接命中。日常开发里这种思路也特别常见，比如缓存热点数据、维护前缀和数组等，本质都是空间换时间。把最小栈这个题想透了，再遇到类似设计题，思路会开阔很多。

2. 解法一：辅助栈（双栈法）设计与完整实现

2.1 同步栈与不同步栈：两种辅助栈设计变体

辅助栈法的核心设计有两种变体，我建议你先掌握第一种，因为它逻辑最简单，面试时最不容易出错。

第一种是“同步压栈”：主栈 push 一个元素时，无论它是否比当前最小值小，辅助栈都压入“当前全局最小值”。比如当前最小值为 2，现在 push 一个 5，辅助栈照样 push 2。这样主栈和辅助栈高度完全相同，pop 时两边同时 pop，根本不需要额外的判断条件，代码非常清爽。

第二种是“只在更小/相等时压栈”：当新元素比辅助栈栈顶（当前最小值）小或相等时，才向辅助栈压入；否则辅助栈不动。这样可以节省一些空间，因为重复的、较大的元素不会占用辅助栈。但代价是，pop 时需要判断当前弹出的元素是否等于辅助栈栈顶，如果相等，才把辅助栈也弹出。这个判断在代码里看似简单，实际上是最容易写错的地方，尤其是用Integer对象比较时，稍不注意就会踩坑。

我个人的建议是：面试或者刷题阶段，直接用同步压栈方案。它很好解释，逻辑也不容易出 bug。节省的那点空间在算法题里根本不重要，面试官更在意的是你能不能写出稳定、正确的代码。

2.2 同步压栈完整代码实现

这里用三种主流语言各写一版，方便你对照。先看 Java 版本，我推荐用ArrayDeque而不是老的Stack类，性能更好，接口也更现代：

class MinStack { Deque<Integer> stack; Deque<Integer> minStack; public MinStack() { stack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); } public void push(int val) { stack.push(val); if (minStack.isEmpty()) { minStack.push(val); } else { minStack.push(Math.min(val, minStack.peek())); } } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }

C++ 版本更简洁一些，直接用标准库的stack：

class MinStack { private: stack<int> stk; stack<int> minStk; public: MinStack() {} void push(int val) { stk.push(val); if (minStk.empty() || val <= minStk.top()) { minStk.push(val); } else { minStk.push(minStk.top()); } } void pop() { stk.pop(); minStk.pop(); } int top() { return stk.top(); } int getMin() { return minStk.top(); } };

Python 版本可以直接用 list 模拟栈：

class MinStack: def __init__(self): self.stack = [] self.min_stack = [] def push(self, val: int) -> None: self.stack.append(val) if not self.min_stack: self.min_stack.append(val) else: self.min_stack.append(min(val, self.min_stack[-1])) def pop(self) -> None: self.stack.pop() self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]

注意 Java 版本中Math.min(val, minStack.peek())这种写法，本质上就是同步压栈：即使新元素更大，辅助栈压入的依然是旧的最小值。这样辅助栈的每个位置都对应主栈在该位置时的全局最小值。

2.3 复杂度分析与正确性验证

时间复杂度方面，四个操作都只涉及栈顶的 push、pop、peek，复杂度都是O(1)。这一点很好理解。空间复杂度是O(n)，辅助栈最多存储 n 个元素，n 为已经 push 的元素个数。

验证正确性最好的方式是手动跑一遍状态变化。我们依次执行以下操作，看两个栈的变化：

从表里能清楚看到，辅助栈的栈顶就是主栈当前的最小值。弹出 4 之后，辅助栈也随之弹出 3，getMin依然能正确返回 3。这就是“同步记录历史”的威力：即使弹出的是最小值，辅助栈栈顶也恰好是上一个状态的最小值，完全不需要额外恢复操作。

3. 解法二：差值法（常数空间优化）的思路与实现

3.1 差值法的核心数学原理

辅助栈方案简单、稳定，但它需要一个额外的栈，空间复杂度是O(n)。如果面试官追问“能不能少用一份空间？”，你就得拿出第二个方案：用差值法把空间利用压到极致。

差值法的思路是：主栈里不直接存原始元素，而是存“当前元素与当前最小值的差值”。同时用一个变量min记录当前的最小值。具体规则如下：

• 栈为空时，第一个元素直接入栈，这里存一个0，同时令min = x；
• 栈非空时，对于新元素x，计算差diff = x - min，并将diff入栈；
• 如果diff < 0，说明x比当前最小值还小，则更新min = x；
• getMin直接返回min。

初看可能觉得绕，但核心逻辑在于：栈里存的是“差值”，而不是元素本身。为什么这样可以呢？因为x和min之间存在线性关系，知道其中一个和差值，就能反推另一个：

• 如果栈顶差值diff >= 0，说明入栈时元素不小于当时的最小值，那么当前栈顶“实际元素”就是min + diff；
• 如果栈顶差值diff < 0，说明入栈时这个元素本身就是新的最小值，那么当前栈顶“实际元素”就等于min。

弹出的时候更巧妙。看栈顶差值diff：

• 如果diff >= 0，说明当前弹出的元素大于等于最小值，那么弹出它不会影响min，直接弹就好了；
• 如果diff < 0，说明当前弹出的元素正是最小值所在，弹出后最小值要“回退”到上一个最小值。而旧最小值和当前元素的关系是diff = x_new - old_min，因此old_min = x_new - diff。又因为弹出时x_new就是当前的min，所以new_min = min - diff。

你看，整个过程中，我们只用了栈本身和一个变量，就实现了所有操作。这就是差值法的核心数学基础。

3.2 必须注意的边界与溢出问题

差值法虽然省了空间，但边界细节比辅助栈多得多，这里要重点强调几个坑：

第一个坑是溢出。我们用diff = x - min，Java 的int范围是-2^31到2^31-1。如果x是2147483647，min是-2147483648，两者的差已经超过int的表示范围。所以实际写代码时，要把diff用long来存，否则会算错。这是我亲手踩过的坑，在力扣上就是“Wrong Answer”，非常隐蔽。

第二个坑是栈为空时调用getMin或top，这是非法的，力扣不会测这种情况，但面试时最好主动和面试官确认一下题目的约束条件。

第三个坑是弹出后恢复最小值时，min - diff这个操作也可能会超出int范围，所以min本身也建议用long来存，最后返回时再转回int。

3.3 差值法完整代码与运行过程模拟

下面是 Java 实现，注意long的使用：

class MinStack { Deque<Long> stack; long min; public MinStack() { stack = new ArrayDeque<>(); } public void push(int val) { long x = val; if (stack.isEmpty()) { stack.push(0L); min = x; } else { stack.push(x - min); if (x < min) { min = x; } } } public void pop() { long diff = stack.pop(); if (diff < 0) { min = min - diff; } } public int top() { long diff = stack.peek(); if (diff > 0) { return (int)(min + diff); } else { return (int)min; } } public int getMin() { return (int)min; } }

C++ 实现也是同样的思路，用long long避免溢出：

class MinStack { private: stack<long long> stk; long long minVal; public: MinStack() {} void push(int val) { long long x = val; if (stk.empty()) { stk.push(0); minVal = x; } else { stk.push(x - minVal); if (x < minVal) minVal = x; } } void pop() { long long diff = stk.top(); stk.pop(); if (diff < 0) { minVal = minVal - diff; } } int top() { long long diff = stk.top(); if (diff > 0) return (int)(minVal + diff); return (int)minVal; } int getMin() { return (int)minVal; } };

我们手动模拟一遍这个流程。依次执行以下操作：

从这个表格可以看出，差值法确实只用一个栈加一个变量就完成了所有操作，空间复杂度降到了O(1)。但也能看出它的问题：整个逻辑对“差值符号”的依赖很强，而且可读性明显不如辅助栈。面试时如果面试官不追问，我个人更建议用辅助栈作为首选答案，差值法作为一个补充亮点展示即可。

3.4 两种解法的选型对比

这里直接给一张对比表，方便你记忆：

如果这是在线笔试，我建议直接写辅助栈，保命要紧。如果是现场面试，我会先写辅助栈，然后主动提一句“如果限制空间，可以改用差值法”，再在面试官追问时详细展开。这样既展示了扎实的基础，又体现了思维深度。

4. 力扣刷题与面试实战：常见问题与排查技巧

4.1 高频 Bug 清单与排查思路

这题代码量不大，但我在实际刷题和看别人代码时，发现几个高频 Bug，这里全部列出来，你可以对照自查。

第一个 Bug 是不同步辅助栈时，pop 判断写错。很多人会写成if (stack.peek() == minStack.peek())，这在 Java 里用Integer类型比较时，大于 127 的值会返回 false，导致辅助栈弹出逻辑失效。正确的做法是用equals方法，或者干脆用同步压栈方案，从根源上回避这个问题。

第二个 Bug 是辅助栈判空顺序写反。比如在push时写成if (val <= minStack.peek())，但如果minStack是空的就会抛异常。记住：永远先判空，再访问栈顶。

第三个 Bug 是差值法里忘了把diff转成long。如果题目测试数据里有极端大数，比如2147483647和-2147483648，int溢出算出的差值完全错误，整个栈就废了。这个 Bug 非常隐蔽，因为大多数测试用例都是普通数字，只有上万个极端数据才能测出来。

第四个 Bug 是 pop 之后没有更新min。辅助栈方案如果同步弹出就不会有这个错，但如果你采用了“只在更小/相等时压栈”的变体，又忘了在弹出最小值时把辅助栈也弹出，那么getMin会一直返回已经不在栈里的值。

4.2 从最小栈延伸出去：hot100 栈题串联思路

最小栈虽然在力扣上标的是中等难度，但它是 hot100 里非常基础的一道栈设计题。刷这题时，我强烈建议你顺便把几个相关的栈题一起过一遍，形成知识网络，效果比孤立刷题好得多。

• 20. 有效的括号：考察栈的最基本用法——匹配与消除，是栈入门第一题。
• 739. 每日温度：单调栈的典型应用，维护一个递减栈来找到右侧第一个更大的元素。
• 42. 接雨水：经典难题，用单调栈计算面积，和最小栈中“维护最小值状态”的思路有异曲同工之妙。
• 155. 最小栈：偏向“数据结构设计”，要求多个操作协调、状态可回退。

你会发现，最小栈的核心思想是“用辅助结构维护状态”，这和单调栈维护“单调性状态”、括号匹配维护“期望状态”本质上一脉相承。能把这几道题串起来理解，你对栈的理解会上升一个层次。

4.3 面试官可能会追问的问题怎么答

这题在面试里被追问的频率很高，我整理了几个常见的 follow-up，以及一个比较稳的回答思路。

第一个追问：如果不用额外空间，怎么实现O(1)的getMin？这就是前面说的差值法。你把差值法的原理讲清楚，说明为什么用long存储差值可以避免溢出，基本上就能让面试官满意。

第二个追问：如果支持并发访问怎么办？这是一个开放题。你可以说在push、pop、getMin上加锁，或者用ConcurrentLinkedDeque加原子变量维护min。这类问题考察的是工程意识，不要求标准答案，关键是展示你对线程安全的理解。

第三个追问：既然辅助栈能轻松实现，为什么不直接封装一个类？这个问题有点“陷阱”意味。你可以回答：正是因为它本质上是一个可供复用的“数据结构”，所以这题才叫“最小栈”——它考察的就是你设计一个类的能力，体现在构造函数、方法签名、状态一致性这些细节上。你可以顺便提一下，你的实现中MinStack类本身不依赖额外全局变量，所有状态都封装在实例内部，这也是面向对象设计中“高内聚”的体现。

5. 实操心得与刷题建议

这题已经刷过很多遍了，每次带人刷题时，我都会强调一个动作：拿张纸，把栈的状态变化一步步画出来。不管是辅助栈里的两个栈，还是差值法里的那个差值栈 +min变量，你只要能把每一步的数据变化画清楚，代码几乎是水到渠成的事，根本不用背。

另外一个小技巧是，如果你发现自己写出来的代码在力扣上“Wrong Answer”，不要急着看题解，而是构造一个包含大量 push、pop、getMin 交替操作的小数据，手动跑一遍，往往很快就能定位问题。这种“手动模拟栈状态”的能力，刷题阶段非常重要，笔试时的调试速度全靠它撑着。

还有一个经验是，力扣 hot100 里的题不需要按顺序刷，按主题刷效率更高。把最小栈和括号匹配、单调栈相关题目放在同一天做，你会明显感觉到知识点之间的迁移效率很高。反过来，如果你只是零散地刷题，今天一道栈明天一道二叉树，大脑很难形成系统性的记忆。

最后想说，这题给我最大的收获是“状态可回退”这四个字。以前写代码，总觉得记录一个变量就万事大吉，最小栈让我意识到：任何需要“回退”的场景，都需要一个记录历史的载体。这个思想在算法题里无处不在，比如函数调用栈、编辑器的撤销重做、浏览器的前进后退，本质上都是“线性历史回退”。想通了这一点，你刷的就不只是一道题，而是一类问题的共性规律。