算法训练营Day18|有效的括号

题目链接：https://leetcode.cn/problems/valid-parentheses/ 视频讲解：https://www.bilibili.com/video/BV1AF411w78g

题目理解

• 给定一个只包含'(',')','{','}','[',']'的字符串s

• 判断字符串是否有效（括号匹配）

• 有效条件：

  1. 左括号必须用相同类型的右括号闭合

  2. 左括号必须以正确的顺序闭合

  3. 每个右括号都有一个对应的左括号

第一想法

思路：栈（Stack）

核心思想：后进先出（LIFO）

• 遇到左括号（(,{,[），压入栈

• 遇到右括号（),},]），检查栈顶：

  • 如果栈为空 → 不匹配，返回false

  • 如果栈顶是对应的左括号 → 弹出栈顶

  • 否则 → 不匹配，返回false

• 遍历结束后，栈必须为空（所有括号都匹配）

C++实现

class Solution { public: bool isValid(string s) { stack<char> st; for (char c : s) { if (c == '(' || c == '{' || c == '[') { st.push(c); } else { if (st.empty()) return false; char top = st.top(); st.pop(); if (c == ')' && top != '(') return false; if (c == '}' && top != '{') return false; if (c == ']' && top != '[') return false; } } return st.empty(); } };

易错提醒

• 忘记检查栈是否为空（直接st.top()会崩溃）

• 只检查了数量，没检查顺序（如"([)]"）