栈算法题分类解析

1. 基础应用类（括号匹配 & 消消乐）

类型特点：这类题目是栈最直接的应用，利用栈来存储需要“匹配”或“抵消”的元素。当遍历到某个特定类型的元素（如右括号、重复项、碰撞的小行星）时，与栈顶元素进行比较或消除。

难度	题目	核心思路简介
简单	20. 有效的括号	遇到左括号入栈，右括号则与栈顶匹配，匹配失败则无效
简单	1047. 删除字符串中的所有相邻重复项	类似消消乐，当前字符与栈顶相同则栈顶出栈，否则入栈
中等	735. 小行星碰撞	模拟碰撞规则，正向右行，负向左行，根据大小决定栈中元素的去留
中等	394. 字符串解码	使用两个栈分别存储数字和字符串，处理嵌套的编码规则

2. 表达式求值类

类型特点：栈是计算表达式的经典工具，特别是对于后缀表达式（逆波兰式），遇到数字入栈，遇到运算符则弹出操作数计算并将结果重新入栈。

难度	题目	核心思路简介
中等	150. 逆波兰表达式求值	数字入栈，遇到运算符则弹出两个元素计算，结果入栈
中等	224. 基本计算器	使用栈处理括号和符号，实现带加减和括号的表达式计算
困难	227. 基本计算器 II	处理加减乘除四则运算，无括号，需考虑运算符优先级

3. 单调栈类

类型特点：这是栈的一个进阶技巧。栈内元素保持单调递增或递减。常用于解决下一个更大/更小元素、每日温度、柱状图中最大矩形等问题。其核心思想是在入栈时破坏单调性的元素，往往就是找到答案的时刻 。

难度	题目	核心思路简介
中等	739. 每日温度	单调递减栈，当遇到比栈顶大的温度时，即可计算出栈顶需要等待的天数
简单	496. 下一个更大元素 I	单调栈预处理 nums2 中每个元素的下一个更大元素，存入哈希表
中等	503. 下一个更大元素 II	循环数组的处理技巧：将数组“拉直”，遍历两遍或使用取模运算
困难	84. 柱状图中最大的矩形	单调递增栈，以每个柱子高度为矩形高的最大扩展宽度
困难	42. 接雨水	单调递减栈，当出现比栈顶高的柱子时，计算凹槽接水量

4. 栈的设计类

类型特点：要求实现特定功能的栈，除了基本的栈操作外，还需要在常数时间内获取最小值或对栈进行特定操作。

难度	题目	核心思路简介
中等	155. 最小栈	使用辅助栈存储当前最小值，或使用一个栈存储差值来实现
中等	232. 用栈实现队列	双栈实现 FIFO，输入栈与输出栈的配合
中等	225. 用队列实现栈	单队列或双队列，通过元素重新入队实现 LIFO
中等	341. 扁平化嵌套列表迭代器	在构造函数中将嵌套列表逆序入栈，hasNext 时展平

5. 进阶与特殊应用类

类型特点：栈与其他数据结构的结合，或利用栈的特性解决一些特定的算法问题，如去除字母、验证栈序列等。

难度	题目	核心思路简介
中等	316. 去除重复字母	单调栈 + 贪心，在维护栈递增的同时，确保每个字母至少出现一次
中等	946. 验证栈序列	模拟栈的压入与弹出，按照 pushed 顺序入栈，当栈顶与 popped 相同时弹出
困难	895. 最大频率栈	设计数据结构，需要维护频率到对应元素栈的映射，以及元素到频率的映射
中等	1441. 用栈操作构建数组	模拟 Push 和 Pop 操作，比较 target 与当前流数据

---

栈的识别技巧

根据 LeetCode 上的总结，当你遇到以下问题时，应该立即想到栈 ：

1. 匹配问题：括号、标签、路径等嵌套结构。
2. 依赖前一个状态：如编辑器的撤销（Undo）操作，浏览器的后退（Back）功能。
3. 单调性：需要找元素左边或右边第一个比它大/小的元素。
4. 表达式计算：中缀转后缀，或直接计算后缀表达式。

刷题建议

1. 打牢基础：从 20. 有效的括号 和 155. 最小栈 入手，理解栈的基本操作和特点 。
2. 攻克单调栈：这是面试中的重点和难点。建议按照 739. 每日温度 → 496. 下一个更大元素 I → 84. 柱状图中最大的矩形 的顺序练习，逐步深入。
3. 模拟与设计：练习 232. 用栈实现队列 和 946. 验证栈序列，加深对栈工作机制的理解。
4. 拓展进阶：最后挑战 316. 去除重复字母 和 895. 最大频率栈，体会栈与其他算法的结合。