题目描述
思路解析
一句话答案：LeetCode 20 有效的括号的标准解法是栈：从左到右扫字符串，左括号一律压栈，右括号则检查栈顶是否为同类型左括号——匹配就弹栈，不匹配或栈已空直接判非法，扫完后栈恰好为空才算有效。每个字符至多进出栈一次，时间 O(n)、空间 O(n)。
这道题真正在问什么
给一个只含 ()[]{} 六种字符的字符串，判断括号是否有效。有效要满足两条：每个左括号都被同类型的右括号闭合，且闭合顺序正确——后打开的括号必须先闭合，不能交叉。比如 "([]{()}[])" 有效，而 "([)]" 虽然左右数量都配平，却因为交叉闭合而无效。「顺序」这个约束，正是本题不能靠简单计数解决的原因。
为什么计数器不行，非要用栈
只有一种括号时，确实可以用计数器：遇 ( 加一、遇 ) 减一，过程中不许为负、最后归零即可。但三种括号混在一起，计数器只能保证每种数量配平，管不了嵌套顺序——"([)]" 三种计数全部平衡，却是非法的，因为 ) 来的时候最近还没闭合的是 [，类型对不上。
问题的本质是：一个右括号该配的对象，永远是「最近一个还没被闭合的左括号」。这是典型的后进先出关系——最晚进来的最先被处理——而后进先出正是栈这个数据结构的定义。可以说不是我们选择了栈，是题目的匹配规则长成了栈的形状。
扫描过程保持什么不变量
算法从左到右扫一遍：遇到左括号就压栈；遇到右括号就看栈顶——若栈为空，或栈顶左括号类型对不上，立即返回 false，否则弹出栈顶表示这一对成功闭合。全程保持的不变量是：栈里自底向上，恰好是「已经打开、还没闭合」的左括号，且越靠栈顶越新。
有了这条不变量，每一步的判断都有了依据：右括号来时只需要看栈顶一个元素，因为合法的闭合顺序规定它只能关最新打开的那个括号；栈顶配不上就绝无别的补救可能，直接判非法是安全的。
为什么最后还要检查栈是否为空
扫描中途不报错，不代表字符串有效。比如 "((("，全程没有任何配对失败，但三个左括号一直躺在栈里没人来关——左括号有剩余同样是非法的。所以最后一步必须检查栈空：栈空说明每个左括号都被恰好闭合过一次，返回 true；否则返回 false。
对称的另一头是「右括号多了」：比如 ")(" 开局就来右括号，此时栈是空的，没有任何左括号可配。这就是为什么处理右括号时要先判空再取栈顶——漏了判空，轻则逻辑错误，重则数组越界。
复杂度怎么算，还能怎么写得更顺
时间 O(n)：字符串扫一遍，每个字符至多压栈一次、弹栈一次，配对查表是 O(1)。空间 O(n)：最坏情况整串都是左括号，栈要装下全部 n 个字符。
实现上有个小技巧：与其建一张「右括号到左括号」的映射表去核对栈顶，也可以在遇到左括号时直接把它对应的右括号压进栈，之后遇到右括号只需和栈顶比是否相等，逻辑更直白。两种写法复杂度相同，选顺手的即可。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「左括号压栈、右括号配栈顶、最后栈空才合法」，下面每一步都在套它。
准备 · 空栈：开局：一个空栈。指针从字符串最左边开始，一个字符一个字符往右扫。左括号进栈、右括号来配对。
读 · 第 1 个 = (：读到第 1 个字符 (。它是左括号，按规则要压进栈，等以后的右括号来关它。
压栈 · (：压栈。把 ( 放到栈顶，栈里现在是 (。它会一直等到对应的 ) 出现才被弹出。
读 · 第 2 个 = [：读到第 2 个字符 [。它是左括号，按规则要压进栈，等以后的右括号来关它。
压栈 · [：压栈。把 [ 放到栈顶，栈里现在是 ( [。它会一直等到对应的 ] 出现才被弹出。
读 · 第 3 个 = ]：读到第 3 个字符 ]。它是右括号，要去看栈顶那个左括号能不能和它配上。
配对 · ] ↔ [：配对。右括号 ] 需要的左括号是 [，栈顶正好是 [ —— 配上了！弹出栈顶，这一对括号正确闭合。
读 · 第 4 个 = {：读到第 4 个字符 {。它是左括号，按规则要压进栈，等以后的右括号来关它。
压栈 · {：压栈。把 { 放到栈顶，栈里现在是 ( {。它会一直等到对应的 } 出现才被弹出。
读 · 第 5 个 = (：读到第 5 个字符 (。它是左括号，按规则要压进栈，等以后的右括号来关它。
压栈 · (：压栈。把 ( 放到栈顶，栈里现在是 ( { (。它会一直等到对应的 ) 出现才被弹出。
读 · 第 6 个 = )：读到第 6 个字符 )。它是右括号，要去看栈顶那个左括号能不能和它配上。
配对 · ) ↔ (：配对。右括号 ) 需要的左括号是 (，栈顶正好是 ( —— 配上了！弹出栈顶，这一对括号正确闭合。
读 · 第 7 个 = }：读到第 7 个字符 }。它是右括号，要去看栈顶那个左括号能不能和它配上。
配对 · } ↔ {：配对。右括号 } 需要的左括号是 {，栈顶正好是 { —— 配上了！弹出栈顶，这一对括号正确闭合。
读 · 第 8 个 = [：读到第 8 个字符 [。它是左括号，按规则要压进栈，等以后的右括号来关它。
压栈 · [：压栈。把 [ 放到栈顶，栈里现在是 ( [。它会一直等到对应的 ] 出现才被弹出。
读 · 第 9 个 = ]：读到第 9 个字符 ]。它是右括号，要去看栈顶那个左括号能不能和它配上。
配对 · ] ↔ [：配对。右括号 ] 需要的左括号是 [，栈顶正好是 [ —— 配上了！弹出栈顶，这一对括号正确闭合。
读 · 第 10 个 = )：读到第 10 个字符 )。它是右括号，要去看栈顶那个左括号能不能和它配上。
配对 · ) ↔ (：配对。右括号 ) 需要的左括号是 (，栈顶正好是 ( —— 配上了！弹出栈顶，这一对括号正确闭合。
扫描结束 · 栈空：扫完整个字符串，栈正好空了——说明每一个左括号都被正确地关掉、没有多余也没有错配。最终结果：合法 true。
边界先想清：空串合法；只剩左括号（栈非空）或开头就来右括号（空栈）都非法。
三个高频追问：栈 vs 计数器、压「期望右括号」的简化技巧、以及含杂字符的处理。
参考代码
def isValid(s): pairs = {")": "(", "]": "[", "}": "{"} stack = [] for ch in s: if ch in "([{": stack.append(ch) # 左括号压栈 else: if not stack or stack[-1] != pairs[ch]: return False # 空栈/不匹配 stack.pop() # 配对成功弹栈 return not stack # 最后栈空才合法复杂度
- 时间：O(n)，每个字符只进栈/出栈一次，扫一遍
- 空间：O(n)，最坏全是左括号时，栈里要装下 n 个
易错点
面试追问把动画讲成自己的话
追问为什么用栈而不是计数器？
追问能不能压「期望的右括号」来简化？
追问如果还含字母等其它字符呢？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最小栈
LeetCode 155 · 中等 · 沿着 栈 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题