[!info] related notes 算法面试题型 MOC 单调栈 递归 有效括号 删除字符串中的所有相邻重复项 逆波兰表达式求值 基本计算器 最小栈 小行星碰撞 每日温度 柱状图中最大的矩形 接雨水 用栈实现队列 用队列实现栈 原地栈 最长有效括号

栈

栈（Stack）的本质是：

把“最近进入、但还没有处理完的信息”暂存起来，并且优先处理最新那份信息。

一句话记忆：

• 后进先出：Last In First Out，LIFO
• 只在一端操作：入栈 push，出栈 pop，看栈顶 peek/top
• 适合处理：匹配、消除、最近关系、延迟结算

一眼判断：这题是不是栈

看到下面这些信号，要往栈想：

• 当前元素只和“最近的未处理元素”有关
• 出现配对、匹配、合法性判断，比如括号匹配
• 出现消除、碰撞、合并，而且可能连续发生反应
• 要找左边/右边最近一个更大或更小的元素
• 题目本质是在维护一批“等待未来处理”的候选信息

如果你发现：

• 当前元素只会影响前面最近的一部分内容
• 被淘汰的旧元素以后不可能再成为答案
• 处理顺序天然是“最新留下来的先处理”

那它大概率就能往栈上靠。

栈和递归的关系

很多栈题，和递归其实是同一种思维。

因为递归调用时，系统底层本来就在维护一条调用栈。

• 递归写法：系统帮你维护栈
• 非递归写法：你自己维护栈

所以像 DFS、表达式解析、括号嵌套求值这类题，常常都能在“递归”和“显式栈”之间切换。

栈题的核心抽象

栈题通常都在做同一件事：

维护一批“暂时不能立即确定答案”的信息，等未来某个元素出现时再结算。

遍历当前元素 x 时，通常只有三种结果：

• x 自己入栈，等待未来处理
• x 和栈顶发生关系，弹出栈顶
• x 连续和多个栈顶发生关系，直到不能再处理

这就是为什么很多栈题都长这样：

const stack = [];

for (const x of arr) {
    while (stack.length && canReact(stack[stack.length - 1], x)) {
        handleTop(stack, x);
    }

    if (shouldKeep(x, stack)) {
        stack.push(x);
    }
}

这个模板比“记具体题”更重要。

做栈题的固定四问

每道栈题都强制自己按这个顺序思考：

1. 栈里维护的到底是谁

先回答：

• 是字符、数字本身？
• 还是下标、边界、状态？

一般规律：

• 只关心值本身 -> 存值
• 还要算距离、区间、左右边界 -> 存下标

2. 什么情况下入栈

问自己：当前元素在什么情况下会成为“未来候选”？

比如：

• 左括号一定要入栈，等右括号来匹配
• 还没找到右边更大元素的位置要入栈，等以后结算
• 当前小行星如果没被撞碎，要入栈进入后续碰撞流程

3. 什么情况下弹栈

问自己：什么样的栈顶，已经不可能再有价值了？

典型场景：

• 已经被匹配掉
• 已经被消除掉
• 已经找到了右边第一个更大/更小元素
• 已经被当前元素证明“不可能再成为答案”

4. 弹栈时要不要顺便结算答案

有些题弹栈只是删除无效候选。

有些题弹栈的那一刻，答案正好被确定。

比如：

• 括号匹配：弹栈是在消除配对关系
• 每日温度：弹栈时就能确定某一天等几天升温
• 柱状图最大矩形：弹栈时就能确定某个高度能扩的宽度

普通栈和单调栈怎么区分

这是做题时最关键的分叉。

普通栈

当你关心的是：

• 最近未匹配元素
• 配对关系
• 消除 / 碰撞 / 合并
• 表达式上下文
• DFS 过程模拟

本质是：

当前元素和栈顶之间有某种“关系型处理”。

单调栈

当你关心的是：

• 左边 / 右边第一个更大元素
• 左边 / 右边第一个更小元素
• 左右边界
• 哪些候选会被新元素淘汰

本质是：

当前元素和栈顶之间有某种“比较型处理”。

如果你已经明确是在求最近更大/更小，优先跳到 单调栈 去看专题。

一页式速查表

类型	栈里通常放什么	关键动作	先练什么	再练什么
括号匹配	字符 / 左括号	遇右括号时匹配并弹栈	有效括号	最长有效括号
消除 / 碰撞	字符 / 数字	当前元素和栈顶持续反应	删除相邻重复项	小行星碰撞
表达式求值	数字 / 运算符 / 上下文	遇运算符或括号时结算	逆波兰表达式求值	基本计算器系列
单调栈	下标	当前元素淘汰一批旧候选	[[daily-temperatures	每日温度]]
设计题	值 / 辅助最值	双栈或栈队互转	最小栈	用栈实现队列

常见题型总览

1. 括号匹配栈

• 识别信号：合法括号、最近未匹配左括号、嵌套结构
• 关键思路：右括号匹配的一定是最近那个未匹配左括号
• 代表题：有效括号、最长有效括号

题解入口：有效括号、最长有效括号

最小模板：

const stack = [];
const map = {
    ')': '(',
    ']': '[',
    '}': '{'
};

for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
        stack.push(ch);
    } else {
        if (!stack.length || stack[stack.length - 1] !== map[ch]) {
            return false;
        }
        stack.pop();
    }
}

return stack.length === 0;

2. 消除 / 碰撞栈

• 识别信号：相邻消除、连续碰撞、当前元素会影响前面一串元素
• 关键思路：当前元素可能连锁作用于多个旧元素，所以常常必须写 while
• 代表题：删除字符串中的所有相邻重复项、小行星碰撞

题解入口：删除字符串中的所有相邻重复项、小行星碰撞

最小模板：

const stack = [];

for (const x of arr) {
    let alive = true;

    while (alive && stack.length && canReact(stack[stack.length - 1], x)) {
        const top = stack[stack.length - 1];

        if (topIsWeaker(top, x)) {
            stack.pop();
        } else if (samePower(top, x)) {
            stack.pop();
            alive = false;
        } else {
            alive = false;
        }
    }

    if (alive) stack.push(x);
}

3. 表达式求值栈

• 识别信号：操作数、运算符、括号、多层上下文
• 关键思路：把还没算完的部分先存起来，等运算符优先级或括号边界出现再结算
• 代表题：逆波兰表达式求值、基本计算器系列

题解入口：逆波兰表达式求值、基本计算器

逆波兰表达式最小模板：

const stack = [];

for (const token of tokens) {
    if (token === '+' || token === '-' || token === '*' || token === '/') {
        const b = stack.pop();
        const a = stack.pop();
        stack.push(calc(a, b, token));
    } else {
        stack.push(Number(token));
    }
}

return stack[0];

注意顺序：一定是先弹 b，再弹 a，因为栈是后进先出。

4. 单调栈

• 识别信号：最近更大 / 最近更小、左右边界、右边第一个满足大小关系的位置
• 关键思路：新元素到来时，把不可能再成为答案的旧元素弹掉
• 代表题：每日温度、下一个更大元素、柱状图最大矩形、接雨水

题解入口：每日温度、柱状图中最大的矩形、接雨水

求右边第一个更大元素的最小模板：

const ans = new Array(n).fill(-1);
const stack = [];

for (let i = 0; i < n; i++) {
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
        const j = stack.pop();
        ans[j] = i;
    }
    stack.push(i);
}

更完整的方向判断、模板和边界技巧，见 单调栈。

5. 设计题

• 识别信号：要求 O(1) 取最小值 / 最大值，或者用一种结构模拟另一种结构
• 关键思路：主栈负责正常数据流，辅助栈负责额外信息
• 代表题：最小栈、用栈实现队列、用队列实现栈

题解入口：最小栈、用栈实现队列、用队列实现栈

最小栈的核心想法：

• 一个栈存所有元素
• 一个辅助栈存“到当前位置为止的最小值”

普通栈的通用模板

const stack = [];

for (const x of arr) {
    while (stack.length && needProcess(stack[stack.length - 1], x)) {
        processTop(stack, x);
    }

    if (needKeep(x, stack)) {
        stack.push(x);
    }
}

这个模板最适合记住三件事：

• 栈顶和当前元素为什么会发生关系
• 为什么这里必须是 while
• 当前元素处理完以后，是否还要保留到未来

单调栈的通用模板

const stack = [];

for (let i = 0; i < n; i++) {
    while (stack.length && makeTopInvalid(i, stack[stack.length - 1])) {
        const j = stack.pop();
        settleAnswer(j, i);
    }

    stack.push(i);
}

写单调栈时最有用的问题不是“背递增还是递减”，而是：

当前元素到来时，我到底想弹掉什么样的栈顶？

想清楚这个，方向就不会反。

什么时候存值，什么时候存下标

存值

当题目只关心元素本身，不关心位置时：

• 括号匹配
• 字符消除
• 逆波兰表达式求值
• 最小栈

存下标

当题目还需要下面任意一种信息时，优先存下标：

• 计算距离
• 访问原数组值
• 确定左右边界
• 回填答案数组

典型题：

• 每日温度
• 下一个更大元素
• 柱状图最大矩形
• 接雨水

栈题最容易错的地方

1. 栈空时直接取栈顶

每次访问 stack[stack.length - 1] 前，都先判断 stack.length。

2. 该用 while 的地方写成 if

只要当前元素可能连续影响多个旧元素，就必须警惕是不是该写 while。

3. 该存下标却存了值

一旦要算天数差、区间宽度、左右边界，往往都必须存下标。

4. 单调方向记反

不要死背“递增栈/递减栈”的名字，先想：

• 我要找更大还是更小？
• 当前元素来时，我要弹掉什么？

5. 边界没有统一处理

像柱状图最大矩形这类题，常常可以通过：

• 首尾加哨兵
• 或者最后强制清栈

把边界统一掉，代码会稳很多。

做单调栈题时的万能提问

每次卡住时，先问自己：

1. 我要找的是左边还是右边？
2. 我要找的是更大还是更小？
3. 栈里存值还是存下标？
4. 当前元素出现时，谁应该被弹掉？
5. 弹掉时答案是直接确定，还是只是删掉无效候选？

这五个问题想清楚，单调栈基本就能落地。

怎么学习栈

很多人觉得栈简单，但一做题就乱，原因通常不是不会 push/pop，而是：

不知道“栈里到底该维护什么”。

所以学习重点不是操作，而是识别模式。

第 1 阶段：先吃透普通栈

建议先做：

• 有效括号
• 删除字符串中的所有相邻重复项
• 逆波兰表达式求值
• 最小栈

目标：

• 熟悉入栈和弹栈时机
• 熟悉“当前元素只和栈顶发生关系”的模型

第 2 阶段：练会连锁反应

建议再做：

• 小行星碰撞
• 字符串消除类题
• 基本计算器系列

目标：

• 看到“消除 / 碰撞 / 合并”就想到 while + 栈
• 理解为什么当前元素可能连续处理前面多个元素

第 3 阶段：系统学单调栈

建议集中刷：

• 每日温度
• 下一个更大元素 I / II
• 柱状图最大矩形
• 接雨水

目标：

• 理解最近更大 / 最近更小
• 理解为什么很多题都要存下标
• 理解单调栈是在做剪枝和延迟结算

第 4 阶段：做设计题和综合题

建议补：

• 最小栈
• 用栈实现队列
• 用队列实现栈
• 表达式解析类题

栈和队列的区别

• 栈：后进先出，适合处理最近未完成状态
• 队列：先进先出，适合按顺序处理任务

记忆方式：

• 栈像一摞盘子，拿最上面的
• 队列像排队，先来先服务

面试里怎么解释“为什么这题用栈”

如果你需要口头说明，可以直接按这个模板答：

1. 这题当前元素只和最近未处理元素有关
2. 这些未处理元素需要按后进先出的顺序被结算
3. 一旦某个元素被弹出，它以后就不可能再成为答案

这三句话说完整，面试官基本就能听出你是真的理解了。

一段总结

栈不是单纯的 push/pop 题型，而是一种“维护未来候选、按最近顺序结算”的思维工具。

• 匹配 / 消除 / 碰撞 -> 优先想普通栈
• 最近更大 / 最近更小 / 左右边界 -> 优先想单调栈
• 写题时先想清楚：栈里留的是谁，为什么它要留到未来再处理

把这三点练熟，栈题就会从“看起来很多”变成“其实是同一个模板的不同外观”。