括号匹配

括号匹配是栈的典型应用：左括号入栈，右括号必须和栈顶的左括号配对。

扫描字符串时：

• 遇到 (、[、{：入栈
• 遇到 )、]、}：检查栈顶是否是对应的左括号
• 如果栈为空、类型不匹配，立即判定无效
• 扫描结束后，栈也必须为空

这个过程只需要从左到右看一遍。

复杂度

• 时间：O(n)
• 空间：O(n)（最坏情况下所有字符都是左括号）

在动画里看什么

• 上方字符格按扫描顺序移动 i
• 绿色表示已经完成匹配的一对括号
• 红色表示第一个导致失败的位置
• 下方 stack 显示当前还没匹配的左括号