问题说明（含示例）

问题描述：给定一个只包含括号（(、)、{、}、[、]）的字符串 s，判断其是否为有效字符串。有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合；
2. 左括号必须以正确的顺序闭合（嵌套关系正确）；
3. 每个右括号都有对应的相同类型左括号。

示例：

1. 输入：s = "()" → 输出：true（单个括号匹配）。
2. 输入：s = "()[]{}" → 输出：true（多个括号依次匹配）。
3. 输入：s = "(]" → 输出：false（类型不匹配，( 对应 ] 错误）。
4. 输入：s = "([])" → 输出：true（嵌套关系正确，[ 被 () 正确包含）。
5. 输入：s = "([)]" → 输出：false（顺序错误，( 应匹配 )，但中间被 [ 打断）。

解题关键

利用栈（Stack） 的 “先进后出（LIFO）” 特性处理括号的嵌套关系，核心思路：

1. 栈的作用：存储未匹配的左括号，遇到右括号时，通过栈顶元素判断是否匹配。
2. 匹配规则：用字典建立 “右括号→左括号” 的映射（如 ')'→'('），便于快速查找对应关系。
3. 异常情况：
   • 右括号无对应左括号（栈为空时遇到右括号）；
   • 右括号与栈顶左括号类型不匹配；
   • 遍历结束后仍有未匹配的左括号（栈不为空）。

对应代码

class Solution:
    def isValid(self, s: str) -> bool:
        # 优化：长度为奇数时，必然无效（括号成对出现）
        if len(s) % 2 != 0:  ## %表示取余数
            return False
        
        # 建立右括号到左括号的映射，便于快速匹配
        parentheses_map = {
            ')': '(',
            '}': '{',
            ']': '['
        }
        
        stack = []  # 栈：存储未匹配的左括号
        
        for char in s:
            if char in parentheses_map: ## 这里是与字典里的快速匹配
                # 当前字符是右括号：需与栈顶左括号匹配
                # 若栈为空（无左括号）或栈顶不匹配，直接返回False
                if not stack or stack[-1] != parentheses_map[char]:
                    return False
                # 匹配成功，弹出栈顶左括号
                stack.pop()
            else:
                # 当前字符是左括号：压入栈中等待匹配
                stack.append(char)
        
        # 遍历结束后，栈必须为空（所有左括号都已匹配）
        return len(stack) == 0
    

对应的基础知识

实现该算法需掌握以下基础概念与操作：

1. 栈的基本操作

   • 用列表模拟栈：stack.append(char) 实现 “压栈”（左括号入栈），stack.pop() 实现 “弹栈”（匹配成功后移除左括号）；
   • stack[-1] 访问栈顶元素（获取最近未匹配的左括号）。

2. 字典的映射作用

   • 字典 parentheses_map 存储右括号到左括号的对应关系（如 ')' 对应 '('），通过 char in parentheses_map 快速判断字符是否为右括号，通过 parentheses_map[char] 直接获取应匹配的左括号，时间复杂度 O(1)。

3. 条件判断与异常处理

   • 长度为奇数时直接返回 false（括号必须成对出现，优化判断）；
   • 遇到右括号时，先检查栈是否为空（无对应左括号）或栈顶不匹配，及时返回 false。

4. 遍历与最终校验

   • 遍历字符串的每个字符，处理左括号入栈、右括号匹配逻辑；
   • 遍历结束后，栈必须为空（所有左括号都被匹配），否则存在未闭合的左括号，返回 false。

对应的进阶知识

该问题的解决涉及栈的应用与复杂度分析的深层逻辑：

1. 时间与空间复杂度

   • 时间复杂度：O(n)（n 为字符串长度），每个字符仅遍历一次，栈的 append、pop、[-1] 操作均为 O(1)；
   • 空间复杂度：O(n)，最坏情况下（如全为左括号 '(((('），栈需存储所有左括号，占用 O(n) 空间。

2. 栈与嵌套结构的适配性

   • 括号的嵌套关系（如 ([])）本质是 “后出现的左括号先匹配”（[ 比 ( 晚出现，先被 ] 匹配），与栈的 “先进后出” 特性完全吻合，因此栈是处理嵌套结构的最优数据结构。

3. 边界情况的全覆盖

   • 空字符串（s = ""）：长度为 0（偶数），栈为空，返回 true（符合有效定义）；
   • 单括号（s = "(" 或 s = ")"）：长度为 1（奇数），直接返回 false；
   • 交叉嵌套（s = "([)]"）：处理 ) 时，栈顶为 [，不匹配，返回 false，正确识别顺序错误。

4. 与其他数据结构的对比

   • 若用列表模拟队列（先进先出），无法处理嵌套关系（如 ([]) 中 [ 无法优先匹配 ]）；
   • 若用哈希表直接计数（如统计左右括号数量），无法判断顺序是否正确（如 ([)] 左右括号数量相等但无效）。

编程思维与启示

1. “特性匹配” 的数据结构选择：针对嵌套结构，优先选择栈（LIFO），因其特性天然适配 “后入先出” 的匹配逻辑，这是解决括号、表达式解析等问题的通用思路。

2. “映射表” 的效率提升：用字典存储对应关系，避免多重 if-else 判断（如 if char == ')' and stack[-1] == '('），使代码更简洁，且查找效率从 O(1) 级提升。

3. “提前剪枝” 的优化意识：先判断字符串长度是否为奇数，直接排除不可能有效的情况，减少后续无效计算，体现 “优化从边界开始” 的思维。

4. “状态校验” 的完整性：遍历结束后检查栈是否为空，确保所有左括号都被匹配，避免遗漏 “有剩余左括号” 的无效情况，体现对 “全局状态” 的把控。

栈的基础知识（小白能懂版）

一、栈是什么？—— 生活中的 “栈”

栈是一种特殊的容器，它的操作有严格的 “顺序限制”：只能从容器的 “顶部” 放入或取出元素，就像生活中的这些场景：

• 叠盘子：洗完的盘子只能放在最上面（不能插在中间），取盘子时也只能从最上面拿；
• 堆书：新书只能放在书堆的最上面，取书时也先拿最上面的；
• 浏览器的 “后退” 功能：最近访问的页面在 “最上面”，后退时先回到上一个访问的页面。

这些场景的共同特点是：“先进后出”（First In Last Out，简称 FILO）—— 先放进去的元素，最后才能取出来。

二、栈的 3 个核心操作（小白必懂）

栈的操作非常简单，核心只有 3 个（用 Python 的列表模拟栈时，对应这些方法）：

操作名称	作用	Python 列表实现	例子（栈：[1,2,3]，顶部是 3）
压栈（Push）	往栈的顶部添加一个元素	stack.append(元素)	压栈 4 → 栈变为 [1,2,3,4]（顶部是 4）
弹栈（Pop）	从栈的顶部移除并返回一个元素	stack.pop()	弹栈 → 返回 3，栈变为 [1,2]（顶部是 2）
查看栈顶（Peek）	查看栈顶部的元素（不移除）	stack[-1]（列表最后一个元素）	查看栈顶 → 返回 3，栈还是 [1,2,3]

注意：栈没有 “从中间插入” 或 “从中间删除” 的操作，只能操作顶部元素，这是它和列表的核心区别。

三、为什么括号匹配问题需要用栈？

回到括号匹配问题，我们需要处理嵌套关系，比如 ([]) 这种情况：

• 先出现 (，然后出现 [；
• 匹配时，[ 要先被 ] 匹配（后出现的左括号先匹配），再轮到 ( 被 ) 匹配。

这完全符合栈的 “先进后出” 特性：后出现的左括号（[）先被处理（弹出栈），先出现的左括号（(）后被处理。

四、用栈解决括号匹配问题的步骤（小白能看懂的拆解）

以示例 s = "([])" 为例，一步步看栈的作用：

步骤 1：初始化栈和括号映射表

• 栈 stack = []（空栈，等待存放左括号）；
• 映射表 parentheses_map = {')':'(', '}':'{', ']':'['}（右括号对应左括号，方便快速查找）。

步骤 2：遍历字符串的每个字符，用栈处理

1. 第一个字符 '('（左括号）：

   • 左括号需要等待匹配，所以压栈 → stack = ['(']（栈顶是 '('）。

2. 第二个字符 '['（左括号）：

   • 同样需要等待匹配，压栈 → stack = ['(', '[']（栈顶是 '['）。

3. 第三个字符 ']'（右括号）：

   • 右括号需要找对应的左括号，通过映射表知道 ']' 对应 '['；
   • 查看栈顶元素 → 正好是 '['，匹配成功！弹栈（移除栈顶的 '['）→ stack = ['(']。

4. 第四个字符 ')'（右括号）：

   • 映射表显示 ')' 对应 '('；
   • 查看栈顶元素 → 是 '('，匹配成功！弹栈 → stack = []（栈空）。

步骤 3：判断最终结果

遍历结束后，栈是空的（stack = []），说明所有左括号都找到了匹配的右括号 → 返回 true。

五、栈如何处理 “无效情况”？

再看无效示例 s = "([)]"，看看栈如何发现问题：

1. 字符 '(' → 压栈 → stack = ['(']；
2. 字符 '[' → 压栈 → stack = ['(', '[']；
3. 字符 ')' → 右括号，对应左括号是 '('；
   • 查看栈顶 → 是 '['（不是 '('），不匹配 → 直接返回 false（无效）。

通过栈顶的实时检查，能立刻发现 “顺序错误” 的无效情况。

六、栈的其他常见应用（帮助理解）

除了括号匹配，栈还在很多场景中发挥作用：

• 函数调用：比如 A() 调用 B()，B() 调用 C()，执行完 C() 要先返回 B()，再返回 A()，用栈记录函数调用顺序；
• 浏览器后退：访问页面 A→B→C，后退时先回到 B，再回到 A，栈记录访问历史；
• 表达式计算：比如 (1+2)*(3-4)，用栈处理括号和运算符的优先级。

总结：栈的核心要点

1. 特性：先进后出（FILO），只能操作顶部元素；
2. 核心操作：压栈（添加）、弹栈（移除）、查看栈顶；
3. 适合场景：处理嵌套关系、需要 “回溯”（回到上一步）的问题；
4. 在括号匹配中：用栈存储左括号，遇到右括号时通过栈顶判断是否匹配，高效解决嵌套和顺序问题。