栈
栈按后进先出（LIFO）组织元素。本文负责括号匹配、辅助最小栈和单调栈。
1. 面试核心
先记住这几条，再读正文- 后进先出。 栈按后进先出顺序访问元素，
push、pop、peek分别表示入栈、出栈和查看栈顶。 - 嵌套匹配。 栈保存尚未结束的嵌套顺序。匹配多种括号时，右括号必须与栈顶左括号的类型一致，数量相同仍不足以保证合法。卡 · 后进先出与待完成状态
- 最小值维护。 同步记录每层最小值，可让最小值查询达到 O(1)。卡 · 最小栈
- 单调栈成本。 单调栈中每项至多入栈、出栈一次，总时间为 O(n)。卡 · 单调栈
2. 后进先出与待完成状态
越晚出现的左括号越早被匹配，所以适合用栈。
static boolean balanced(String text) {
java.util.Deque<Character> stack = new java.util.ArrayDeque<>();
for (char c : text.toCharArray()) {
if (c == '(') stack.push(c);
else if (c == ')') {
if (stack.isEmpty()) return false;
stack.pop();
}
}
return stack.isEmpty();
}
代码只检查圆括号，忽略其他字符。(a()) 返回 true，)( 和 (() 返回 false。扫描时，栈保存尚未匹配的左括号。时间 O(n)，最坏辅助空间 O(n)。单种括号可改用计数器，同时检查前缀余额与最终余额。
3. 显式栈与调用栈
递归调用按栈保存活动状态，具体机制见递归。显式栈让程序自己管理待处理项。先压右孩子、再压左孩子，可实现根左右顺序。
4. 最小栈
每次入栈时，同时保存此前最小值与新值的较小者。出栈时同步移除一层。辅助栈顶始终是当前全部元素的最小值。查询最小值为 O(1)，额外空间为 O(n)。
输入 2,1,1 时，辅助栈保存 2,1,1。弹出末个 1 后，最小值仍为 1。若只保存最小值变化，遇到相等最小值也需保存或计数。
5. 单调栈
查找每项右侧第一个更大值时，可保存待回答的下标。栈内对应值从底到顶单调不增。新值严格大于栈顶时，弹出栈顶并记录答案。随后将新下标入栈。
输入 [2,2,3]，两个 2 的答案都由 3 给出。相等值保留，才能满足“严格更大”。每个下标入栈一次、出栈至多一次，总时间 O(n)。空间最坏 O(n)。
6. 使用边界
Java ArrayDeque 拒绝 null，空栈 pop 会抛异常。端点 API 的具体约定见队列。栈的空间由同时保留的状态数决定。
7 · 面试题卡片
本页题目与参考回答
7.1 多种括号为何无法只比较左右数量？
考察重点：嵌套次序与类型配对。
相关内容：后进先出与待完成状态。
参考回答
数量相同仍会出现类型次序错误，例如 ([)]。
右括号应与最近尚未匹配的左括号配对。栈保存这个顺序，结束时还需检查是否为空。
7.2 最小栈遇到重复最小值时如何处理？
考察重点：辅助状态与重复值生命周期。
相关内容：最小栈。
参考回答
可以同步保存每一层的最小值。
弹出一个 1 后，下一层仍能保留另一个 1。只保存最小值变化时，应记录相等值或维护计数。
7.3 单调栈中嵌套弹栈为何仍为 O(n)？
考察重点：待回答集合与累计操作次数。
相关内容：单调栈。
参考回答
每个下标至多入栈和出栈各一次，总次数为 O(n)。
一轮可弹出多个元素，但之后这些元素已离开栈。严格更大问题只在新值大于栈顶时弹出。