好的，我们这次来看 LeetCode 第 20 题「有效的括号」。

1. 题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

2. 题目理解与思路分析

关键点：

• 括号有嵌套关系，比如 {[]} 是有效的，但 ([)] 是无效的，因为 [ 被 ( 包含，但 ] 却在 ) 之前出现，顺序错乱。
• 这意味着：后出现的左括号，必须先匹配（后进先出，LIFO），适合用 栈（Stack） 来解决。

匹配规则：

• 遇到左括号（(、[、{）就压入栈。
• 遇到右括号（)、]、}）时：
  • 如果栈为空 → 无效（没有与之匹配的左括号）。
  • 弹出栈顶元素，检查是否与当前右括号匹配（( 对 )，[ 对 ]，{ 对 }），不匹配则无效。
• 遍历完字符串后，栈必须为空，否则说明有左括号没匹配完。

3. 逐步推导示例

以 s = "([{}])" 为例：

1. 字符 '(' → 压栈：['(']
2. 字符 '[' → 压栈：['(', '[']
3. 字符 '{' → 压栈：['(', '[', '{']
4. 字符 '}' → 栈顶是 '{'，匹配 → 弹出栈顶 → 栈：['(', '[']
5. 字符 ']' → 栈顶是 '['，匹配 → 弹出 → 栈：['(']
6. 字符 ')' → 栈顶是 '('，匹配 → 弹出 → 栈空
7. 字符串结束且栈空 → 有效

4. 边界情况考虑

• 空字符串 → 有效（栈空，直接返回 true）。
• 只有左括号，如 "(" → 遍历完栈不为空 → 无效。
• 只有右括号，如 ")" → 遇到右括号时栈空 → 无效。
• 左右括号数量一致但类型不匹配，如 "(]" → 遇到 ] 时栈顶是 (，不匹配 → 无效。
• 嵌套顺序错乱，如 "([)]"：
  • '(' 入栈，'[' 入栈
  • 遇到 ')' 时栈顶是 '['，不匹配 → 无效。

5. 代码实现（Python）

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}  # 右括号到左括号的映射
    
    for char in s:
        if char in mapping:  # 当前字符是右括号
            # 弹出栈顶元素，如果栈空则用占位符（比如'#'）表示不匹配
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:  # 当前字符是左括号
            stack.append(char)
    
    # 最后栈必须为空
    return not stack

解释：

• 使用字典 mapping 存储右括号到左括号的映射，方便匹配检查。
• 遇到右括号时，检查栈顶是否是对应的左括号。
• 时间复杂度 O(n)，空间复杂度 O(n)（最坏情况全是左括号）。

6. 总结

这道题是栈的经典应用，关键在于理解括号匹配的 顺序性 与 嵌套性。
通过栈的 LIFO 特性，可以确保最近未匹配的左括号与当前的右括号匹配。