手帐 Blog

主题

10 · 栈 ​

目标：用数组 push/pop 当栈；会括号匹配、最小栈，并建立单调栈「找下一个更大元素」的直觉。

为什么面试会考 ​

栈考的是 LIFO（后进先出） 能不能变成代码：

  • 括号匹配：最近遇到的左括号要先配对 → 天然是栈。
  • 最小栈：在 O(1) 额外空间里维护「当前最小值」——看你会不会用辅助栈。
  • 单调栈：数组里「下一个更大/更小元素」是前端面试里数组专题的高频延伸（739 是入门）。

会栈，后面 DFS 的迭代写法、表达式求值、撤销栈都有同一套心智。

零基础概念：栈是什么 ​

操作含义JS（数组模拟）
入栈 push放到栈顶stack.push(x)
出栈 pop弹出栈顶stack.pop()
看栈顶 peek只看不弹stack[stack.length - 1]
空栈没有元素stack.length === 0

LIFO：最后 push 进去的，最先 pop 出来。

javascript
const stack = [];
stack.push(1);
stack.push(2);
stack.pop(); // 2
stack.pop(); // 1

JS 没有内置 Stack 类，用数组即可；push/pop 都在尾部，均摊 O(1)。

JS 模板 / 套路 ​

模板 1：括号匹配骨架 ​

javascript
const stack = [];
for (const ch of s) {
  if (是左括号) {
    stack.push(对应右括号);
  } else {
    if (stack.length === 0 || stack.pop() !== ch) return false;
  }
}
return stack.length === 0;

模板 2：单调栈（找下一个更大） ​

维护一个下标递减的栈：当前元素比栈顶大时，栈顶元素的「下一个更大」就是当前元素。

javascript
const stack = []; // 存下标
const ans = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
  while (stack.length && nums[stack.at(-1)] < nums[i]) {
    const j = stack.pop();
    ans[j] = i - j; // 或 nums[i]，看题目要什么
  }
  stack.push(i);
}

精讲 1：LeetCode 20 · 有效的括号 ​

题意：字符串只含 ()[]{}，判断是否合法配对。

思路：遇左括号，把期待的右括号压栈；遇右括号，弹栈比对。最后栈必须空。

javascript
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  const stack = [];
  const pair = { '(': ')', '[': ']', '{': '}' };

  for (const ch of s) {
    if (pair[ch]) {
      stack.push(pair[ch]);
    } else {
      if (stack.length === 0 || stack.pop() !== ch) return false;
    }
  }
  return stack.length === 0;
};
  • 每个字符最多入栈、出栈各一次 → O(n) 时间，O(n) 空间。

精讲 2：LeetCode 155 · 最小栈 ​

题意：实现栈，支持 push、pop、top，且 getMin 要 O(1)。

思路：再维护一个最小栈 minStack，与数据栈同步 push/pop；minStack 栈顶永远是当前最小值。

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

MinStack.prototype.push = function(val) {
  this.stack.push(val);
  const min = this.minStack.length === 0
    ? val
    : Math.min(this.minStack.at(-1), val);
  this.minStack.push(min);
};

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

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

MinStack.prototype.getMin = function() {
  return this.minStack.at(-1);
};
  • 每次操作 O(1)；多占一份最小值记录的空间。

口述一句：「数据栈正常操作，最小栈在 push 时压入当前全局最小，pop 时一起弹。」

精讲 3：LeetCode 739 · 每日温度 ​

题意：temperatures[i] 表示第 i 天温度，求「还要等几天才有更高温度」，没有则 0。

思路（单调栈入门）：栈里存下标，且对应温度单调递减。当天更热时，不断弹栈，被弹出的下标 j 的答案就是 i - j。

javascript
/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
  const n = temperatures.length;
  const ans = new Array(n).fill(0);
  const stack = []; // 存下标，栈内温度递减

  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[stack.at(-1)] < temperatures[i]) {
      const j = stack.pop();
      ans[j] = i - j;
    }
    stack.push(i);
  }
  return ans;
};
  • 每个下标最多入栈、出栈一次 → O(n)。
  • 单调栈套路：维护一个单调递增/递减的结构，用 while 在「破坏单调」时结算答案。

练习清单 ​

题号一句话提示
LeetCode 20. 有效的括号本篇模板 1，左括号压「期待的右括号」
LeetCode 155. 最小栈辅助 minStack 同步 push/pop
LeetCode 739. 每日温度单调递减栈存下标，i - j 是等待天数
LeetCode 496. 下一个更大元素 I单调栈 + 哈希映射元素到下标
LeetCode 84. 柱状图中最大的矩形单调栈进阶（栈存下标，弹栈算宽度）

今日验收 checklist ​

  • [ ] 能默写「有效括号」：遇左压右、遇右弹栈比对
  • [ ] 能讲清最小栈为什么 getMin 是 O(1)
  • [ ] 独立写出 739，并说出「单调递减栈 + 弹栈结算」
  • [ ] 在 LeetCode 用 JS 提交 20、155、739 中至少两道

若你以前见过 ​

C++ 的 stack<int> 在 JS 里就是 const st = []。蓝桥里括号、表达式求值若做过，20 题是同一套；739 的单调栈是数组专题里「比双指针再进一步」的固定套路，后面还会见到。