跳至主要內容

LeetCode 155. 最小栈

Skyme2026/7/15大约 10 分钟刷题Hot 100栈设计

LeetCode 155. 最小栈

题目核心

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

实现 MinStack 类：

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

所有操作都需要在 O(1) 时间复杂度内完成。

解题思考过程

第一步：理解问题

看到这道题，首先想到的是：栈本身是后进先出的结构，push、pop、top 都是 O(1) 操作，但 getMin 怎么做到 O(1)？

如果每次调用 getMin 都遍历整个栈找最小值，那就是 O(n)，太慢了。

第二步：暴力解法（O(n) getMin）

最直接的思路：每次 getMin 时遍历整个栈。

push: O(1) - 直接压栈
pop: O(1) - 直接弹栈
top: O(1) - 返回栈顶
getMin: O(n) - 遍历栈找最小值

这个思路简单，但 getMin 太慢，不符合题目要求。

第三步：思考如何优化 getMin

要让 getMin 变成 O(1)，需要提前记录最小值，而不是每次临时计算。

那什么时候记录呢？

  • push 时：如果新元素更小，更新最小值
  • pop 时：如果弹出的是最小值，需要找到新的最小值

问题在于：pop 时如果弹出了最小值，怎么快速找到上一个最小值？

第四步：想到辅助栈

如果每次 push 时，不仅记录当前元素，还记录到目前为止的最小值，那 pop 时就能直接知道上一个最小值是什么。

这就是辅助栈的思路：

  • 主栈：存储所有元素
  • 辅助栈：存储每个时刻的最小值

这样：

  • push 时：主栈压元素，辅助栈压当前最小值
  • pop 时：主栈弹元素，如果弹出的是最小值，辅助栈也弹
  • getMin 时：直接返回辅助栈顶

第五步：为什么要用 <= 而不是 <

一开始可能会想：如果新元素大于当前最小值，就不压入辅助栈。但这样会有问题：

push(2) -> push(2)

如果用 <，辅助栈只有 [2]
pop() 弹出一个 2，辅助栈也弹出，变成空的
此时 getMin() 就错了，还有一个 2 没被记录

所以必须用 <=，把所有可能成为最小值的元素都记录下来。

第六步：空间优化的思路

辅助栈法需要 O(n) 空间，能不能优化到 O(1)？

想到：能不能不存储额外的栈，而是在现有栈中存储"差值"？

  • 用变量记录当前最小值
  • 栈中存储 val - minVal
  • 这样可以从差值和最小值反推出真实值

这就是差值法的思路。

第七步：验证差值法的正确性

push(3): minVal=3, stack=[0]
push(2): diff=-1, minVal=2, stack=[0, -1]
push(5): diff=3, minVal=2, stack=[0, -1, 3]

top(): diff=3 >= 0, 返回 2 + 3 = 5 ✓
getMin(): 返回 2 ✓

pop(): 弹出 3, diff >= 0, minVal 不变 ✓
pop(): 弹出 -1, diff < 0, minVal = 2 - (-1) = 3 ✓

这个思路是可行的！

第八步：选择最佳方案

三种思路对比：

  1. 全局查找法：pop 时 O(n)，太慢
  2. 辅助栈法：所有操作 O(1)，逻辑清晰
  3. 差值法：所有操作 O(1)，空间 O(1)，但逻辑复杂

面试中优先选择辅助栈法，因为：

  • 逻辑直观，不容易出错
  • 面试官更容易理解
  • 不需要处理溢出等边界情况

解法一：差值法（空间 O(1)）

第一种思路是用一个变量记录当前最小值，栈中不存储真实值，而是存储真实值与当前最小值的差值。

var MinStack = function() {
  this.stack = [];
  this.minVal = 0;
};

MinStack.prototype.push = function(val) {
  if (this.stack.length === 0) {
    this.stack.push(0);
    this.minVal = val;
  } else {
    let diff = val - this.minVal;
    this.stack.push(diff);
    if (diff < 0) {
      this.minVal = val;
    }
  }
};

MinStack.prototype.pop = function() {
  let diff = this.stack.pop();
  if (diff < 0) {
    this.minVal = this.minVal - diff;
  }
};

MinStack.prototype.top = function() {
  let diff = this.stack[this.stack.length - 1];
  if (diff < 0) {
    return this.minVal;
  } else {
    return this.minVal + diff;
  }
};

MinStack.prototype.getMin = function() {
  return this.minVal;
};

差值法代码逐行解释

构造函数

var MinStack = function() {
  this.stack = [];
  this.minVal = 0;
};
  • stack：存储差值的栈，不存储真实值。
  • minVal：记录当前栈中的最小值。

push 方法

MinStack.prototype.push = function(val) {
  if (this.stack.length === 0) {
    this.stack.push(0);
    this.minVal = val;
  }

如果是第一个元素：

  • 差值为 val - val = 0，所以压入 0。
  • 将 val 设为当前最小值。
  } else {
    let diff = val - this.minVal;
    this.stack.push(diff);
    if (diff < 0) {
      this.minVal = val;
    }
  }
};

如果不是第一个元素：

  • 计算差值 diff = val - minVal。
  • 将差值压入栈。
  • 如果差值为负，说明 val 比当前最小值更小，更新 minVal。

pop 方法

MinStack.prototype.pop = function() {
  let diff = this.stack.pop();
  if (diff < 0) {
    this.minVal = this.minVal - diff;
  }
};

弹出栈顶的差值：

  • 如果差值为负，说明刚才弹出的元素是当时的最小值。
  • 需要恢复上一个状态的最小值：旧 min = 当前 min - diff。
  • 因为 diff 是负数，所以 minVal - diff 实际上是加上 diff 的绝对值。

top 方法

MinStack.prototype.top = function() {
  let diff = this.stack[this.stack.length - 1];
  if (diff < 0) {
    return this.minVal;
  } else {
    return this.minVal + diff;
  }
};

获取栈顶元素的真实值：

  • 如果差值为负，说明栈顶元素就是当前最小值（因为它导致了 minVal 更新）。
  • 如果差值为正或零，真实值 = 当前最小值 + 差值。

getMin 方法

MinStack.prototype.getMin = function() {
  return this.minVal;
};

直接返回当前记录的最小值。

差值法的执行过程

以 push(3) -> push(2) -> push(5) 为例：

push(3):
  stack 为空，压入 0，minVal = 3
  stack = [0], minVal = 3

push(2):
  diff = 2 - 3 = -1
  压入 -1，diff < 0，更新 minVal = 2
  stack = [0, -1], minVal = 2

push(5):
  diff = 5 - 2 = 3
  压入 3，diff >= 0，minVal 不变
  stack = [0, -1, 3], minVal = 2

top():
  diff = 3 >= 0，返回 2 + 3 = 5

getMin():
  返回 2

pop():
  弹出 3，diff >= 0，minVal 不变
  stack = [0, -1], minVal = 2

pop():
  弹出 -1，diff < 0，minVal = 2 - (-1) = 3
  stack = [0], minVal = 3

top():
  diff = 0，返回 3 + 0 = 3

getMin():
  返回 3

差值法的优缺点

优点缺点
空间复杂度 O(1)（除输入栈外）代码逻辑较难理解，容易出错
不使用额外栈差值可能溢出（JavaScript 无此问题）
所有操作 O(1)需要仔细处理边界情况

解法二：辅助栈法（最常用）

第二种思路是使用两个栈：主栈存储所有元素，辅助栈存储对应时刻的最小值。

var MinStack = function () {
  this.stack = [];
  this.min_stack = [];
};

MinStack.prototype.push = function (val) {
  this.stack.push(val);

  if (
    this.min_stack.length === 0 ||
    val <= this.min_stack[this.min_stack.length - 1]
  ) {
    this.min_stack.push(val);
  }
};

MinStack.prototype.pop = function () {
  const val = this.stack.pop();

  if (val === this.min_stack[this.min_stack.length - 1]) {
    this.min_stack.pop();
  }
};

MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function () {
  return this.min_stack[this.min_stack.length - 1];
};

辅助栈法代码逐行解释

构造函数

var MinStack = function () {
  this.stack = [];
  this.min_stack = [];
};
  • stack：主栈，存储所有元素。
  • min_stack：辅助栈，存储每个时刻的最小值。

push 方法

MinStack.prototype.push = function (val) {
  this.stack.push(val);

先把值压入主栈。

  if (
    this.min_stack.length === 0 ||
    val <= this.min_stack[this.min_stack.length - 1]
  ) {
    this.min_stack.push(val);
  }
};

关键：如果辅助栈为空，或者新来的值小于等于辅助栈顶元素，就把它压入辅助栈。

为什么要用 <= 而不是 <：

如果有重复的最小值，必须都记录下来。例如：

push(2) -> push(2)

辅助栈应该是 [2, 2]，而不是 [2]

这样 pop 第一个 2 后，辅助栈还有一个 2，最小值仍然正确。

pop 方法

MinStack.prototype.pop = function () {
  const val = this.stack.pop();

  if (val === this.min_stack[this.min_stack.length - 1]) {
    this.min_stack.pop();
  }
};

弹出主栈元素后，如果弹出的是当前最小值（等于辅助栈顶），辅助栈也要弹出。

top 方法

MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

直接返回主栈栈顶元素。

getMin 方法

MinStack.prototype.getMin = function () {
  return this.min_stack[this.min_stack.length - 1];
};

直接返回辅助栈栈顶元素，也就是当前最小值。

辅助栈法的执行过程

以 push(3) -> push(2) -> push(2) -> push(5) 为例：

push(3):
  stack = [3], min_stack = [3]

push(2):
  2 <= 3，压入辅助栈
  stack = [3, 2], min_stack = [3, 2]

push(2):
  2 <= 2，压入辅助栈（注意用的是 <=）
  stack = [3, 2, 2], min_stack = [3, 2, 2]

push(5):
  5 > 2，不压入辅助栈
  stack = [3, 2, 2, 5], min_stack = [3, 2, 2]

getMin(): 返回 2

pop():
  弹出 5，5 != 2，辅助栈不变
  stack = [3, 2, 2], min_stack = [3, 2, 2]

pop():
  弹出 2，2 == 2，辅助栈弹出
  stack = [3, 2], min_stack = [3, 2]

getMin(): 返回 2

pop():
  弹出 2，2 == 2，辅助栈弹出
  stack = [3], min_stack = [3]

getMin(): 返回 3

辅助栈法的优缺点

优点缺点
逻辑清晰，容易理解和维护空间复杂度 O(n)，需要额外栈
代码简洁，不容易出错辅助栈可能存储较多重复元素
所有操作 O(1)

解法三：全局查找法（pop 时 O(n)）

第三种思路是用一个变量记录最小值和它的下标，弹出最小值时重新遍历整个栈找新的最小值。

var MinStack = function () {
  this.topIndex = -1;
  this.min = null;
  this.minIndex = null;
  this.stack = [];
};

MinStack.prototype.push = function (value) {
  this.stack.push(value);
  this.topIndex++;

  if (this.min > value || this.min === null) {
    this.min = value;
    this.minIndex = this.topIndex;
  }
};

MinStack.prototype.pop = function () {
  let value = this.stack.pop();

  if (this.stack.length === 0) {
    this.min = null;
    this.minIndex = -1;
    this.topIndex--;
    return;
  }

  if (this.topIndex == this.minIndex) {
    this.min = this.stack[0];
    this.minIndex = 0;
    for (let i = 0; i < this.stack.length; i++) {
      if (this.stack[i] < this.min) {
        this.min = this.stack[i];
        this.minIndex = i;
      }
    }
  }

  this.topIndex--;
};

MinStack.prototype.top = function () {
  return this.stack[this.topIndex];
};

MinStack.prototype.getMin = function () {
  return this.min;
};

全局查找法代码逐行解释

构造函数

var MinStack = function () {
  this.topIndex = -1;
  this.min = null;
  this.minIndex = null;
  this.stack = [];
};
  • topIndex：栈顶指针。
  • min：当前最小值。
  • minIndex：最小值所在的下标。
  • stack：主栈，存储所有元素。

push 方法

MinStack.prototype.push = function (value) {
  this.stack.push(value);
  this.topIndex++;

  if (this.min > value || this.min === null) {
    this.min = value;
    this.minIndex = this.topIndex;
  }
};

压入元素后，如果新元素更小（或栈为空），更新最小值和它的下标。

pop 方法

MinStack.prototype.pop = function () {
  let value = this.stack.pop();

  if (this.stack.length === 0) {
    this.min = null;
    this.minIndex = -1;
    this.topIndex--;
    return;
  }

如果弹出后栈为空，重置所有状态。

  if (this.topIndex == this.minIndex) {
    this.min = this.stack[0];
    this.minIndex = 0;
    for (let i = 0; i < this.stack.length; i++) {
      if (this.stack[i] < this.min) {
        this.min = this.stack[i];
        this.minIndex = i;
      }
    }
  }

  this.topIndex--;
};

关键：如果弹出的是最小值（topIndex == minIndex），需要重新遍历整个栈找到新的最小值。

top 和 getMin 方法

MinStack.prototype.top = function () {
  return this.stack[this.topIndex];
};

MinStack.prototype.getMin = function () {
  return this.min;
};

直接返回对应的值。

全局查找法的执行过程

以 push(3) -> push(2) -> push(5) 为例：

push(3):
  stack = [3], topIndex = 0, min = 3, minIndex = 0

push(2):
  2 < 3，更新 min = 2, minIndex = 1
  stack = [3, 2], topIndex = 1

push(5):
  5 > 2，不更新
  stack = [3, 2, 5], topIndex = 2, min = 2, minIndex = 1

pop():
  弹出 5，topIndex = 1，1 != 1？不相等，因为弹出前 topIndex == minIndex？
  等等，弹出前 topIndex = 2，minIndex = 1，不相等，所以不需要重新查找
  stack = [3, 2], topIndex = 1

pop():
  弹出 2，弹出前 topIndex = 1，minIndex = 1，相等！
  需要重新遍历找最小值：
  min = 3, minIndex = 0
  stack = [3], topIndex = 0, min = 3, minIndex = 0

全局查找法的问题

这种方法的 pop 操作在最坏情况下是 O(n) 时间复杂度：

push(1) -> push(2) -> push(3) -> ... -> push(n)

此时 min = 1, minIndex = 0

如果连续 pop，每次都要重新遍历整个栈：
pop(1): 需要遍历 n-1 个元素
pop(2): 需要遍历 n-2 个元素
...
总时间：O(n²)

三种解法对比

解法pushpoptopgetMin空间复杂度特点
差值法O(1)O(1)O(1)O(1)O(1)空间最优，但逻辑复杂
辅助栈法O(1)O(1)O(1)O(1)O(n)最常用，逻辑清晰
全局查找法O(1)O(n)O(1)O(1)O(1)pop 操作慢，不推荐

为什么辅助栈法是最佳选择

虽然差值法空间更优，但辅助栈法有以下优势：

  1. 逻辑直观：看到代码就能理解，不容易出错。
  2. 易于维护：过了很久再看也能快速理解。
  3. 不依赖语言特性：差值法在某些语言中可能会有溢出问题。
  4. 面试首选：面试官更希望看到清晰易懂的解法。

辅助栈法的优化

如果想减少辅助栈的空间占用，可以存储下标而不是值：

var MinStack = function () {
  this.stack = [];
  this.min_stack = [];
};

MinStack.prototype.push = function (val) {
  this.stack.push(val);

  if (
    this.min_stack.length === 0 ||
    val <= this.stack[this.min_stack[this.min_stack.length - 1]]
  ) {
    this.min_stack.push(this.stack.length - 1);
  }
};

MinStack.prototype.pop = function () {
  this.stack.pop();

  if (this.stack.length === this.min_stack[this.min_stack.length - 1]) {
    this.min_stack.pop();
  }
};

MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function () {
  return this.stack[this.min_stack[this.min_stack.length - 1]];
};

这种方式辅助栈存储的是下标，节省了一点空间（但空间复杂度仍然是 O(n)）。

使用示例

const minStack = new MinStack();

minStack.push(-2);
minStack.push(0);
minStack.push(-3);

minStack.getMin();  // 返回 -3
minStack.pop();
minStack.top();     // 返回 0
minStack.getMin();  // 返回 -2

执行过程（辅助栈法）：

push(-2):
  stack = [-2], min_stack = [-2]

push(0):
  0 > -2，不压入辅助栈
  stack = [-2, 0], min_stack = [-2]

push(-3):
  -3 <= -2，压入辅助栈
  stack = [-2, 0, -3], min_stack = [-2, -3]

getMin(): 返回 min_stack[-1] = -3

pop():
  弹出 -3，-3 == -3，辅助栈弹出
  stack = [-2, 0], min_stack = [-2]

top(): 返回 stack[-1] = 0

getMin(): 返回 min_stack[-1] = -2
路的尽头依旧是路
Copyright © 2026 Skyme