栈与单调栈

讲解

栈是只在一端进出的线性结构：后进先出（LIFO）。它匹配的问题都有一种「嵌套 / 对称 / 最近」的气味：括号匹配（最近的开括号先闭合）、函数调用栈、撤销操作、表达式求值、路径化简。JS 里用数组加 push/pop 就是栈——记住只碰尾部，别用 shift/unshift（那是 O(n) 的头部操作）。

括号匹配类问题的通法值得单独记：遇到开括号入栈，遇到闭括号检查栈顶是否配对、配对则弹出，最后栈空才算合法。三个错误来源——闭括号时栈空、栈顶不匹配、结束时栈非空，分别对应「多了闭括号」「类型交错」「多了开括号」。这个框架能套到所有「成对消去」的问题上。

单调栈是栈的进阶形态：栈内元素保持单调（递增或递减），用来回答「每个元素右侧第一个比它大 / 小的元素是谁」。以每日温度为例：栈里存「还没找到答案的下标」，对应温度单调递减；新温度一高过栈顶，栈顶元素的答案就确定了（当前下标 - 栈顶下标），弹出结算。每个下标最多入栈出栈一次，总复杂度 O(n)——比每个元素都向右扫描的 O(n²) 快一个量级。另一个经典应用是最小栈：用辅助栈同步记录「当前栈的最小值」，让 getMin 也做到 O(1)。

示例

三道代表：有效括号（配对消去）、每日温度（单调递减栈求「下一个更大元素」）、最小栈（辅助栈）：

import assert from 'node:assert/strict';

function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else if (stack.pop() !== pairs[ch]) {
      return false; // 栈空或不配对都在这里失败
    }
  }
  return stack.length === 0; // 有剩余开括号也不合法
}

// 单调栈：栈内下标对应温度递减；新温度更高时结算栈顶
function dailyTemperatures(temperatures) {
  const answer = new Array(temperatures.length).fill(0);
  const stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const j = stack.pop();
      answer[j] = i - j;
    }
    stack.push(i);
  }
  return answer; // 留在栈里的下标答案保持 0
}

// 最小栈：mins 栈顶始终是当前数据栈的最小值
class MinStack {
  constructor() {
    this.data = [];
    this.mins = [];
  }
  push(x) {
    this.data.push(x);
    if (this.mins.length === 0 || x <= this.mins[this.mins.length - 1]) {
      this.mins.push(x); // 等于也要入栈，否则重复最小值弹出时会错位
    }
  }
  pop() {
    const x = this.data.pop();
    if (x === this.mins[this.mins.length - 1]) this.mins.pop();
  }
  top() {
    return this.data[this.data.length - 1];
  }
  getMin() {
    return this.mins[this.mins.length - 1];
  }
}

assert.strictEqual(isValid('()[]{}'), true);
assert.strictEqual(isValid('(]'), false);
assert.strictEqual(isValid('([)]'), false);
assert.strictEqual(isValid(''), true);

assert.deepStrictEqual(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]), [1, 1, 4, 2, 1, 1, 0, 0]);

const ms = new MinStack();
ms.push(-2);
ms.push(0);
ms.push(-3);
assert.strictEqual(ms.getMin(), -3);
ms.pop();
assert.strictEqual(ms.top(), 0);
assert.strictEqual(ms.getMin(), -2);

console.log('栈示例全部通过');

单调栈记住一句话：「新元素结算栈顶」。想找右侧第一个更大元素就维护递减栈，想找第一个更小元素就维护递增栈——把「更大 / 更小」翻译成栈的单调方向，是这类题唯一的记忆点。

常见坑

• 用 shift/unshift 当栈操作：数组头部操作是 O(n)，栈只用 push/pop 这对尾部操作。
• 括号匹配漏了结尾检查：循环结束栈非空说明开括号多余，必须 return stack.length === 0。
• MinStack 的辅助栈用 < 而不是 <=：相等的最小值不入辅助栈，pop 掉一个后最小值就提前「复活」错了。
• 单调栈里存值还是存下标分不清：要算距离（如隔几天）必须存下标；只关心值时可以存值，但存下标两种信息都有。
• 看到「下一个更大」就双重循环：这正是单调栈的识别信号，先想 O(n) 解法再动手。

小结

栈 = 尾部进出的 LIFO，匹配「嵌套 / 最近 / 成对消去」类问题；单调栈用「新元素结算栈顶」求每个元素的右侧边界，O(n) 解决下一个更大元素家族。下一章看栈的对偶：队列与单调队列。