第十八天 有效的括号

栈的经典应用，建议先去了解栈的基础
题目链接：https://leetcode.cn/problems/valid-parentheses/ 视频讲解：https://www.bilibili.com/video/BV1AF411w78g

一、看到题目的第一想法

1. 题目要求理解：给定一个只包含'('、')'、'{'、'}'、'['、']'的字符串，判断字符串中的括号是否有效。规则是：
   • 左括号必须用相同类型的右括号闭合；
   • 左括号必须以正确的顺序闭合；
   • 每个右括号都必须有对应的左括号。
2. 核心思路：这是一道典型的栈应用题目，栈的 “后进先出” 特性正好能匹配括号的嵌套关系：
   • 遇到左括号时，把它压入栈中；
   • 遇到右括号时，检查栈顶是否是对应的左括号，如果是则弹出栈顶，否则直接返回false；
   • 遍历结束后，栈为空说明所有括号都匹配成功，字符串有效。
3. 初步实现念头：
   • 先用n % 2 == 1快速过滤掉长度为奇数的字符串，因为奇数长度的字符串一定无法完全匹配。
   • 用一个unordered_map来存右括号和对应左括号的映射关系，这样遇到右括号时可以直接查表找对应的左括号。
   • 遍历字符串，遇到左括号压栈，遇到右括号检查栈顶是否匹配。

二、实现过程中遇到的困难

1. 栈操作的边界条件
   • 一开始忘记处理 “栈为空时遇到右括号” 的情况，比如字符串开头就是')'，直接访问stk.top()会导致程序崩溃。后来加上了stk.empty()的判断，保证取栈顶前栈非空。
   • 遍历结束后，忘记判断栈是否为空，比如字符串"(()"遍历结束后栈里还有一个'('，但一开始直接返回true，导致错误。
2. 映射关系的方向搞反
   • 一开始错误地把pairs写成了左括号到右括号的映射，遇到右括号时无法直接查表找到对应的左括号，导致匹配逻辑混乱。后来改成了 “右括号 → 左括号” 的映射，这样遇到右括号时，直接用pairs[ch]就能拿到对应的左括号，和栈顶元素对比。
3. 分支逻辑的混乱
   • 一开始把if-else的条件写反了，比如把 “遇到右括号” 的逻辑写到了else分支里，导致遇到左括号时执行了匹配右括号的代码，压栈和弹栈的逻辑完全颠倒。
   • 一开始没有用pairs.count(ch)来判断是否是右括号，而是用了多个if条件判断字符类型，代码非常冗余，后来才想到用哈希表简化判断。
4. 特殊用例的遗漏
   • 一开始没考虑空字符串""，后来发现代码里return stk.empty()天然处理了这个情况，返回true，符合题目要求。
   • 没考虑括号类型不匹配的情况，比如"(]"，一开始没有对栈顶元素和映射值进行对比，导致这类错误用例也返回了true。

三、今日收获心得

1. 栈在括号匹配问题中的核心应用这道题让我彻底理解了栈的 “后进先出” 特性在处理嵌套结构时的优势：栈顶元素永远是最近遇到的左括号，正好和下一个遇到的右括号进行匹配。这种思路不仅适用于括号匹配，还能推广到 HTML 标签匹配、表达式求值等场景。
2. 哈希表简化条件判断的技巧用unordered_map来存右括号和对应左括号的映射，把原本需要多个if-else的判断逻辑，简化成了查表操作，让代码更简洁、更易维护，也降低了出错的概率。
3. 边界条件的重要性这道题的很多错误都来自边界条件：奇数长度、栈空取栈顶、遍历后栈非空等。通过这次实现，我养成了写代码前先列清楚所有边界情况的习惯，避免了程序崩溃和逻辑错误。
4. 代码结构的优化意识学会了用 “快速过滤（奇数长度）→ 核心逻辑（栈 + 哈希表）→ 最终校验（栈空）” 的结构来组织代码，让逻辑层次更清晰，可读性更强。
5. 对算法复杂度的理解加深整个算法的时间复杂度是 \(O(n)\)，每个字符只需要入栈 / 出栈一次；空间复杂度是 \(O(n)\)，最坏情况下（全是左括号）栈需要存下所有字符。这种线性复杂度的解法，是这类问题的最优解之一。