题目链接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; stackchar stk; // 用于存储左括号的栈 // 建立右括号到左括号的映射方便匹配检查 unordered_mapchar, 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(); } };