题目链接：https://leetcode.cn/problems/valid-parentheses/ 视频讲解：https://www.bilibili.com/video/BV1AF411w78g
一、 题目核心分析与思路
题目要求：判断一个只包含括号字符(, ), [, ], {, }的字符串s是否为“有效”的。有效的标准是：
类型匹配：左括号必须用相同类型的右括号闭合。
顺序正确：左括号必须以正确的顺序闭合。
一一对应：每个右括号都必须有一个对应的左括号。
核心思路 - 栈（Stack）的应用：
括号匹配问题具有“最近相关性”或“后进先出”的特性。最后出现的、未被匹配的左括号，必须优先与最先出现的、与其匹配的右括号进行匹配。这正是栈（Stack）数据结构的典型应用场景。
算法步骤：
初始化：创建一个空栈，用于存放遍历过程中遇到的左括号。
遍历字符串：
遇到左括号
(, [, {：将其压入栈（push）。遇到右括号
), ], }：需要检查栈顶元素。如果栈为空，说明没有左括号与之匹配，字符串无效。
如果栈顶元素与当前右括号不匹配，说明括号类型顺序错误，字符串无效。
如果栈顶元素与当前右括号匹配，则将栈顶元素弹出（pop），表示这一对括号匹配成功。
最终检查：遍历完成后，如果栈为空，说明所有左括号都找到了匹配的右括号，字符串有效；如果栈不为空，说明还有多余的左括号未被匹配，字符串无效。
边界情况处理：
左括号多余：遍历结束，栈不空。（如
"((())"）右括号多余：遇到右括号时，栈已空。（如
"())"）括号类型不匹配：遇到右括号时，栈顶左括号与之不配对。（如
"([)]"）
优化技巧：
剪枝：如果字符串长度是奇数，则一定无法完全匹配，可以直接返回
false。
#include <stack> #include <unordered_map> #include <string> using namespace std; class Solution { public: bool isValid(string s) { // 优化：长度为奇数的字符串一定无效 if (s.size() % 2 != 0) return false; stack<char> stk; // 用于存储左括号的栈 // 建立右括号到左括号的映射，方便匹配检查 unordered_map<char, char> pair = { {')', '('}, {']', '['}, {'}', '{'} }; for (char c : s) { if (pair.count(c)) { // 当前字符c是右括号 // 如果栈为空，或栈顶元素不匹配当前右括号对应的左括号 if (stk.empty() || stk.top() != pair[c]) { return false; // 匹配失败 } stk.pop(); // 匹配成功，弹出栈顶左括号 } else { // 当前字符c是左括号 stk.push(c); } } // 遍历结束，栈空则全部匹配成功 return stk.empty(); } };
