教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文是「宫水三叶的刷题日记」系列LogicStack-LeetCode 仓库中 LeetCode 第 20 题的深度题解。题目本身是判断由()[]{}六种括号组成的字符串是否有效属于最简单的栈应用之一但其背后涉及的「栈的选型」「哈希表映射」「ASCII 差值技巧」「括号匹配问题的通用套路」等内容却是后续 32、22、678 等多道括号系难题的基石。读完本文你将掌握括号匹配的两套可运行解法、JDK 栈的正确用法以及如何把同一思路推广到更复杂的括号问题上。一、题目描述与判定规则给定一个只包括(、)、{、}、[、]的字符串s判断字符串是否有效。有效字符串需满足两条硬性规则左括号必须用相同类型的右括号闭合——(只能被)闭合[只能被]闭合{只能被}闭合不能出现交叉混配左括号必须以正确的顺序闭合——后出现的左括号要优先被闭合即满足「后进先出」的栈式匹配顺序。示例一览示例输入输出直观解释示例 1s ()true一对直接相邻的合法括号示例 2s ()[]{}true多对括号依次并列互不干扰示例 3s (]false类型不匹配违反规则 1示例 4s ([)]false[被)错误闭合顺序混乱违反规则 2示例 5s {[]}true括号层层嵌套后进先出恰好匹配数据范围提示$1 \le s.length \le 10^4$s仅由括号字符()[]{}组成。这意味着字符串最长可达一万个字符算法必须在线性时间内完成扫描任何 $O(n^2)$ 的朴素思路如对每个右括号向前暴力查找左括号在极端输入下都会超时也正因如此栈这种「一次扫描、$O(1)$ 入出栈」的数据结构成为天然的正解。二、解法一栈 哈希表标准思路这是道模拟题同一类型的括号一个右括号要对应一个左括号。扫描时维护一个栈遇到左括号(、{、[直接入栈遇到右括号时检查栈顶是否为对应的左括号若匹配则弹出栈顶说明这一对闭合成功若不匹配或栈已空则整个字符串无效立即返回false扫描结束后若栈为空说明所有括号都配对完成返回true若栈中仍有残留的左括号说明存在未被闭合的括号返回false。右括号到左括号的对应关系用一个哈希表固化下来即可。完整 Java 代码与原题解一致可直接提交class Solution { HashMapCharacter, Character map new HashMapCharacter, Character(){{ put(], [); put(}, {); put(), (); }}; public boolean isValid(String s) { DequeCharacter d new ArrayDeque(); for (int i 0; i s.length(); i) { char c s.charAt(i); if (c ( || c { || c [) { d.addLast(c); } else { if (!d.isEmpty() d.peekLast() map.get(c)) { d.pollLast(); } else { return false; } } } return d.isEmpty(); } }关键细节解读哈希表的方向键是右括号、值是左括号这样在遇到右括号时可以 $O(1)$ 查出它「应该匹配谁」用map.get(c)与栈顶做比对判断左括号的方式这里用c ( || c { || c [三次直接比较。更简洁的等价写法是判断map.containsValue(c)但直接比较在字符集固定只有三种左括号时反而可读性更好空栈保护!d.isEmpty()必须放在左侧因为map.get(c)对任意右括号都有值真正可能出错的是空栈时peekLast()抛异常一旦右括号来袭而栈已空说明该右括号没有可配对的左括号直接判定非法最终判空return d.isEmpty()覆盖了「全部匹配」与「左括号多余」两种情况无需再单独维护计数器。复杂度分析时间复杂度$O(n)$对字符串s完整扫描一遍每个字符至多入栈、出栈各一次空间复杂度哈希表只存 3 对映射大小固定不随输入规模增长为 $O(1)$栈在极端情况如s ((((((...全是左括号下会退化为 $O(n)$但就本题「栈」本身而言算法额外数据结构是 $O(1)$ 哈希表 线性栈。三、解法二栈 ASCII 差值省掉哈希表的技巧原题解的第二套做法不需要哈希表利用的是同类型左右括号在 ASCII 值上「接近」不同类型之间「远离」的事实。ASCII 差值原理括号类字符的 ASCII 码如下右侧同时给出相对于字符0的偏移即代码中c - 0的结果字符ASCII 码相对0(48) 的偏移同类差值(40-8与)差 1)41-7与(差 1[9143与]差 2]9345与[差 2{12375与}差 2}12577与{差 2观察可以发现一条重要性质同类型的左右括号ASCII 差值不超过 2而不同类型的左右括号差值必然大于 2。例如(与]相差 53、[与)相差 50、{与)相差 82均远超 2。于是判断「栈顶左括号是否与当前右括号匹配」这件事可以完全跳过哈希表改为判断二者的 ASCII 距离是否 $\le 2$。完整 Java 代码class Solution { public boolean isValid(String s) { DequeInteger d new ArrayDeque(); for (int i 0; i s.length(); i) { char c s.charAt(i); int u c - 0; if (c ( || c { || c [) { d.addLast(u); } else { if (!d.isEmpty() Math.abs(d.peekLast() - u) 2) { d.pollLast(); } else { return false; } } } return d.isEmpty(); } }与解法一的对比维度栈 哈希表栈 ASCII 差值匹配判定方式栈顶 map.get(右括号)Math.abs(栈顶 - 当前) 2额外数据结构一张 3 键哈希表无纯算术判定可读性语义直白几乎不会写错需要理解 ASCII 编码规律属于「背结论」型技巧可移植性任何语言均可照搬依赖字符编码ASCII/UTF-8 前 128 位在统一编码环境下同样通用需要特别说明的是ASCII 差值法依赖括号字符在编码表中的布局六种括号恰好被设计为同组相邻、异组远离这属于语言字符集的客观事实而非巧合。也正是因为这一点三叶在题解中将其作为「节省一个哈希表」的优化手段而哈希表方案则语义更清晰适合作为面试时的首选讲解版本。两种写法的时间复杂度均为 $O(n)$空间复杂度均为 $O(1)$不含栈本身的线性退化场景。四、为什么用 Deque 而不是 Stack这是本题题解中三叶特别强调的一个工程细节值得单独成节三叶使用了Deque双端队列来充当栈而不是Stack这也是 JDK 推荐的做法。建议所有的 Java 同学都采用Deque作为栈。原因有二Stack继承自Vector拥有动态数组的全部公共 API这意味着Stack除了push/pop/peek之外还能调用add、remove、get等任意数组操作。栈的语义只能从栈顶进出被完全破坏——使用者可以在任意位置增删元素栈的「后进先出」约束形同虚设这在工程上是不安全的Stack犯了面向对象设计的错误Stack是「组合」has-a内部持有容器却错误地实现成了「继承」is-a直接继承Vector属于 JDK 早期的历史遗留设计缺陷。因此正确的做法是使用Deque接口 ArrayDeque实现Deque接口只暴露双端队列能力addLast/pollLast/peekLast从类型层面就杜绝了破坏栈语义的可能ArrayDeque底层是循环数组无容量上限自动扩容性能优于Vector后者方法带synchronized同步开销。对照本仓库 Index/栈.md 中收录的十余道栈专题题目可以看到这一选型贯穿整个系列无论是 155. 最小栈 的双栈设计还是 232. 用栈实现队列 的双栈模拟题解代码统一采用DequeInteger d new ArrayDeque()的风格这正是该系列在代码质量上的统一追求。五、从 20 题出发栈思路在括号系列中的延伸20 题是整个括号问题家族的地基。栈「后进先出」的匹配本质可以沿两个方向演化出更复杂的解法本仓库均有对应题解延伸一栈里存下标——32. 最长有效括号困难20 题只问「是否有效」32 题则要「最长有效的连续子串有多长」。解法依旧用栈但入栈的不再是括号字符而是左括号的下标扫描到(时入栈其下标i扫描到)时弹出栈顶与之匹配然后用「当前位置i减去新的栈顶下标或哨兵j」计算这段有效子串的长度并更新答案其本质是栈里只存放待匹配的(下标虽然这些下标在原字符串中不连续但任意两个相邻栈元素之间的区间必然是有效括号因此栈顶下标天然可以作为有效区间的左边界。这正是 20 题「栈 出栈配对」逻辑的量变到质变——把「是否匹配」升级成了「匹配区间有多长」。延伸二得分/计数的抽象——22. 括号生成中等 与 678. 有效的括号字符串中等22 题要求生成所有有效的括号组合其 DFS 剪枝思想可以视为 20 题的「逆向」令左括号得分 1、右括号得分 -1则合法组合必须满足最终得分为 0、且过程中得分始终非负——这与 20 题栈中左括号永不「欠债」是同一枚硬币的两面。678 题则引入了*通配符可视为(、)或空串此时单靠一个栈已不够用解法升级为维护「最低得分l与最高得分r」的区间模拟*令l减一、r加一过程中若l为负则归零、若l r则提前返回false。可以看到这仍然是 20 题「左右括号必须配对且顺序正确」规则在含通配符场景下的推广。延伸三括号问题的完整地图本仓库用两份 Index 文件把括号系题目按标签归档Index/栈.md收录 20、32、155、232、341、385、591、636、726、735、856、946、1106、1190 等全部栈专题题目附难度与推荐指数Index/括号问题.md收录 20、22、32、301、678 等括号匹配/生成/删除专题。这两份索引本身就是「刷穿 LeetCode」系列最重要的导航入口——每个条目都指向仓库内对应的完整题解 Markdown读者可以按标签体系逐题刷穿。六、总结与刷题建议回到第 20 题本身本题是栈这一数据结构的「入门口试必考题」值得掌握的三件事两种解法都要会哈希表映射版语义清晰、作为面试首选ASCII 差值版体现对字符编码的敏锐度可作为加分亮点栈的选型要正确Java 环境一律DequeArrayDeque远离历史遗留的Stack这一点与仓库 Index/栈.md 中所有题解的风格保持一致匹配逻辑的骨架要背熟左括号入栈、右括号查栈顶、空栈即非法、结束必判空——这四步同时是 32 题存下标求最长、22 题得分剪枝生成、678 题区间得分处理通配符等进阶题目的共同基础。一道简单题串联起的是整个「括号 栈」知识网络。仓库 README.md 中说明这是一个日更的算法题解仓库LeetCode 目录按题号分片存放全部题解Index 目录则提供按 Tag 分类的速查索引建议读者在刷完 20 题后顺着 Index/括号问题.md 依次攻克 22、32、678、301完成从简单到困难的完整闭环。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode-Book 精选题解栈与哈希表 O(1) 匹配秒解「有效的括号」LeetCode Book 精选题解栈与哈希表 O 1 匹配秒解「有效的括号」 导读 「有效的括号」是《Krahets 笔面试精选 88 题》中考察 栈S文档/教程algorithm-base 栈与队列专题LeetCode 20 有效的括号——动画图解两种栈解法与原理剖析algorithm base 栈与队列专题LeetCode 20 有效的括号——动画图解两种栈解法与原理剖析 本文是 algorithm base 仓库「栈和AI 技能AI 插件金融科技AlgoNote 题解精讲 | LeetCode 0032「最长有效括号」动态规划与栈双解法深度解析AlgoNote 题解精讲 | LeetCode 0032「最长有效括号」动态规划与栈双解法深度解析 本文是 AlgoNote「算法通关手册」系列题解之一围教程文档知识库上一篇30 seconds of code 实战用 every 与 some 对 JavaScript 数组做真值Truthy/Falsy检查下一篇LX Music音源终极配置指南3分钟解锁全网无损音乐创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考