手帐 Blog

主题

复盘 · LC 155 最小栈 ​

题目 ​

题意 ​

设计支持 push、pop、top、getMin 的栈，且 getMin 必须 O(1)。

  • 题目保证 pop / top / getMin 在非空栈上调用。
  • 边界：连续压入递减序列；弹出后最小值要「回退」到上一个最小；相同最小值出现多次。

涉及算法 ​

标签一句话
辅助栈 / 同步记录数据栈之外再记「当前最小值历史」
设计题每个 API 都要 O(1)，空间换时间

教程对照：10 · 栈 精讲 2 就是最小栈。

评价我的解法 ​

你没有用教程里的双栈，而是用 this.min 链表回溯上一段最小值，并在栈元素上挂 minNode：只有「刷新最小值」的那次 push 才挂节点，pop 时若挂了节点就把 min 拨回 pre。逻辑能 AC（约 69%），说明你理解「最小值要可回退」。

我的代码（摘自 155-最小栈/index.js，不含本地测例）：

javascript
var MinStack = function () {
  this.stack = [];
  /* 链表 */
  this.min = null;
};

MinStack.prototype.push = function (value) {
  if (!this.min) {
    this.min = {
      value,
      pre: null,
    };
    this.stack.push({
      value,
      minNode: this.min,
    });
  } else if (this.min.value > value) {
    const oldMin = this.min;
    this.min = {
      value,
      pre: oldMin,
    };
    this.stack.push({
      value,
      minNode: this.min,
    });
  } else {
    this.stack.push({
      value,
      minNode: null,
    });
  }
};

MinStack.prototype.pop = function () {
  if (this.stack.length === 0) {
    return null;
  }
  const node = this.stack[this.stack.length - 1];
  if (node.minNode) {
    this.min = this.min.pre;
  }
  this.stack.pop();
};

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

MinStack.prototype.getMin = function () {
  if (!this.min) {
    return null;
  }
  return this.min.value;
};

对在哪：

  1. 新最小值才建链节点，弹出时按链回退——等价于「最小值变化历史」。
  2. 相等时不刷新（> 而不是 >=）：重复最小值靠「第一次建的节点」撑着，多次 pop 中间层也不会误拨，处理正确。

糙在哪：

  1. 实现偏重：每个元素一个对象 + 最小链节点，内存约 5%；面试标准答是同步最小栈两行 push/pop。
  2. 注释写「链表」：实际是最小值历史的单链，和数据栈是两套结构，口述时容易绕。
  3. 空栈返回 null：LeetCode 保证合法调用，可省略；pop 题面是 void，不必 return null。

小结：会做，但应换成教程双栈版默写——更短、更好讲、空间也更可预期。

最佳题解 ​

数据栈 + 最小栈同步：

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

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  this.stack.push(val);
  const min =
    this.minStack.length === 0
      ? val
      : Math.min(this.minStack[this.minStack.length - 1], val);
  this.minStack.push(min);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  this.stack.pop();
  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];
};
  • 每次操作 O(1)，空间 O(n)。
  • 为何更优：与数据栈等长同步，pop 时一起弹，getMin 永远看 minStack 顶；无链表指针、无「这次要不要挂 minNode」分支。
  • 空间优化版：最小栈只在 val <= 当前最小 时压入（注意用 <= 处理重复最小），你今天的链思路接近这一档，但双数组仍更好写。

关联题目 ​

题为何相关
20. 有效的括号同一套栈 API 手感
739. 每日温度栈进阶：单调栈
716. 最大栈对称题：维护最大值（了解即可）

一句话带走 ​

最小栈面试优先讲：数据栈 + 最小栈同步 push/pop，栈顶即当前最小。