20. 有效的括号

题目链接：20. 有效的括号

题目描述

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

有效字符串需满足：

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

核心思考：栈机制与哈希表映射

判断括号是否有效，是一个典型的后进先出 (LIFO) 场景：最后被打开的左括号，必须最先被对应的右括号闭合。因此，这是**栈（Stack）**发挥威力最经典的应用。

为了让代码更优雅，摒弃冗长丑陋的 if-elif-else 分支，最优实践是引入哈希表映射：

• 哈希表（字典）：维护右括号对左括号的映射关系（如 ")": "("）。这让我们能在遇到一个字符时，只需判断它是不是哈希表的键，就能立刻断定它是左括号还是右括号。
• 栈的运作流程：
  1. 遍历字符串：每次遇到左括号，将其直接压入栈中。
  2. 遇到右括号时，开始匹配校验：尝试从栈顶弹出一个元素。如果栈已经空了，或者弹出的左括号与此时哈希表映射的值不一致，直接判定无效并返回 False。
  3. 注意为了防止在栈空时执行 pop() 抛出异常，可以给一个虚拟的出栈值（比如 '#'）来代替以简化代码逻辑。
• 收尾校验：当整个字符串遍历结束后，如果原本的所有左括号都被顺利匹配并弹出了，栈此时一定为空并返回 True；如果栈内还有残留的元素（比如说明左括号过多没有右括号来匹配），则返回 False。

解题思路 (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        # 使用字典存储映射关系：键为右括号，值为左括号
        mapping = {")": "(", "]": "[", "}": "{"}

        for char in s:
            if char in mapping:
                # 遇到右括号：弹出栈顶元素。若栈为空，赋一个非括号的虚拟值避免 IndexError
                top_element = stack.pop() if stack else '#'
                
                # 校验栈顶的左括号是否与当前右括号匹配
                if mapping[char] != top_element:
                    return False
            else:
                # 遇到左括号：直接入栈
                stack.append(char)

        # 遍历结束后，栈为空说明全部匹配成功
        return not stack

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是字符串 s 的长度。我们只需要遍历一遍字符串，每次栈操作（append 和 pop）以及哈希表查找的均摊时间复杂度都是 $O(1)$，因此整体消耗线性时间。
• 空间复杂度：$O(N)$。最坏情况下（字符串全是左括号，如 "((((("），栈会满载所有字符，占用 $O(N)$ 的空间。字典占用常数级别的极小空间（只存储了 3 对固定映射）。