01先读懂这个概念
为什么总是找最近的左括号
读字符串 [()]。遇到 [ 时，这个方括号还没结束；遇到 ( 时，又出现了一个更里面的任务。下一个 ) 必须结束最近的 (，不能越过它去结束外层 [。这就是后进先出：LIFO。
栈只需要从同一端操作。把左括号压入栈顶叫 push；关闭它时从栈顶取出叫 pop；查看栈顶而不删除叫 peek。在 Python 中可以用 list 的 append、pop 和 [-1] 表达这些操作。
只计数为什么不够
对于只有一种括号的某些问题，可以用计数维护未关闭的数量；但多种括号还必须保存次序。([)] 的左、右括号数量相同，却不能正确嵌套。当读到 ) 时，最近的未关闭左括号是 [，类型不匹配。
把栈理解为『尚未完成、且有嵌套顺序的事情』，后面递归调用、表达式求值和单调栈都能套用这个含义。先说明栈里每个元素代表什么，再决定什么时候压入或弹出。
02从具体数据开始手算
拿一个小输入，逐步手算
检查 [()]，栈从左到右表示栈底到栈顶。
| 读到 | 动作 | 栈 | 解释 |
|---|---|---|---|
| 开始 | 无 | [] | 没有未关闭括号 |
| [ | push | ['['] | 外层未完成 |
| ( | push | ['[','('] | 内层未完成 |
| ) | 匹配并 pop | ['['] | 先关闭内层 |
| ] | 匹配并 pop | [] | 再关闭外层 |
扫描结束且栈空才算合法。如果输入只有 [(，扫描途中没有右括号冲突，但仍有未完成任务，因此必须返回 false。
03把正确性的理由说清楚
栈内保存了什么
- 每一步之前，栈按出现顺序保存所有尚未匹配的左括号。
- 左括号建立一个新的待完成任务；右括号必须关闭栈顶任务。空栈或类型不同都说明不可能正确嵌套。
- 全部字符处理完后，栈空等价于所有任务都已正确关闭。
04把刚才的思路写成代码
基础课用 Python 表达，先对照变量含义与执行顺序。后续算法课提供 Python、C++ 与 JavaScript 三种实现。
def valid_brackets(text):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in text:
if char in '([{':
stack.append(char)
elif char in pairs:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
else:
return False
return not stack代码里的每个关键决定
pairs = {')': '(', ']': '[', '}': '{'}- 右括号作为键，查询它应该匹配哪一种左括号。这里用到了之前学习的键值表。
if not stack or stack[-1] != pairs[char]:- 先检查是否为空，再读取栈顶；短路求值保证空栈时不会访问 [-1]。这里只接受三种括号，其余字符视为非法输入。
return not stack- 即使途中没有错误，也必须检查是否还有没关掉的左括号。空串在这个约定下是合法的。
05这些操作要付出多少代价
把工作量具体数出来
每个字符处理一次，左括号最多入栈一次、出栈一次，总时间 O(n)，list 尾部追加按摊还常数分析。
最坏输入全部为左括号，栈中同时保存 n 个字符，所以辅助空间 O(n)。
不要在栈底删除来模拟 pop。栈顶放在数组末尾，才能避免把后面的元素全部向前移动。
06用一个反例检查理解
数量相等不代表合法嵌套
([)] 中各类左右括号数量相同，但是 ) 到来时栈顶为 [，不能跨越它匹配更早的 (。
怎样修正：保存类型与顺序，用栈顶做匹配；也别忽略以右括号开头和以未关闭左括号结束的情况。
07自己推一次，再做自测
定位第一次失败
分别手算 {[]} 和 {[}]，指出第二个字符串在哪一个字符处失败，当时栈是什么。
需要一点提示
关注右括号 } 到来时，最近未关闭的是谁。
查看完整推导与答案
- {[]} 的状态为 ['{'] → ['{','['] → ['{'] → []，合法。
- {[}] 在第三个字符 } 处失败，此时栈为 ['{','[']。
- } 需要栈顶为 {，但当前是 [；无需继续扫描就可判断非法。