好的，我们这次来详细讲解 LeetCode 第 20 题：有效的括号（Valid Parentheses）。

这是一道非常经典的栈（Stack）应用题目，也是学习数据结构和算法时的一个基础且重要的例题。

1. 题目描述

题目链接：LeetCode 20 - Valid Parentheses
难度：简单
标签：栈、字符串

题目描述：

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

有效字符串需满足：

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

示例 1：
输入：s = "()"
输出：true

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

示例 3：
输入：s = "(]"
输出：false

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

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

2. 题目理解与思路分析

2.1 核心问题

我们要检查括号的匹配是否合法。

• 遇到左括号时，需要等待一个匹配的右括号。
• 后出现的左括号，需要先被匹配（后进先出，Last In First Out），这提示我们可以用栈来存储左括号。

2.2 思路步骤

1. 创建一个空栈。
2. 遍历字符串中的每个字符：
   • 如果是左括号（(、[、{），将其压入栈中。
   • 如果是右括号（)、]、}）：
     • 若栈为空，说明没有左括号与之匹配，返回 false。
     • 若栈不为空，弹出栈顶元素，检查是否与当前右括号匹配：
       • 匹配则继续；
       • 不匹配则返回 false。
3. 遍历结束后，检查栈是否为空：
   • 栈为空 → 所有括号都匹配完成 → 返回 true。
   • 栈不为空 → 有左括号未被匹配 → 返回 false。

3. 匹配规则设计

我们可以用一个哈希表（字典）来存储括号的对应关系，这样代码更清晰。

匹配规则：

• ')' 匹配 '('
• ']' 匹配 '['
• '}' 匹配 '{'

4. 逐步推演示例

示例 1：s = "()[]{}"

1. 遇到 '(' → 入栈：栈 = ['(']
2. 遇到 ')' → 栈顶是 '('，匹配 → 弹出栈顶，栈 = []
3. 遇到 '[' → 入栈：栈 = ['[']
4. 遇到 ']' → 匹配 → 弹出，栈 = []
5. 遇到 '{' → 入栈：栈 = ['{']
6. 遇到 '}' → 匹配 → 弹出，栈 = []
7. 遍历结束，栈为空 → true。

示例 2：s = "([)]"

1. '(' 入栈：栈 = ['(']
2. '[' 入栈：栈 = ['(', '[']
3. 遇到 ')' → 栈顶是 '['，不匹配 ')' → 返回 false。

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

6. 复杂度分析

• 时间复杂度：O(n)，n 是字符串长度，每个字符只处理一次。
• 空间复杂度：O(n)，最坏情况下（全是左括号）栈的大小为 n。

7. 边界情况考虑

• 空字符串 → 栈为空 → 返回 true。
• 只有左括号，如 "(((" → 最后栈不为空 → false。
• 只有右括号，如 "))" → 第一次遇到右括号时栈为空 → false。
• 左右括号数量匹配但顺序不对，如 "([)]" → 在匹配阶段就会失败。

8. 总结

这道题的核心是理解栈的后进先出特性与括号匹配顺序的一致性。
通过维护一个栈，我们可以高效地检查括号的有效性。
这是栈的一个非常直接且经典的应用场景，掌握它有助于解决更复杂的嵌套结构问题。

希望这个逐步的推导能帮助你完全理解这道题！如果还有疑问，我们可以再深入讨论。