力扣hot100（37）栈-有效的括号

核心思想：为什么必须用栈？

一句话：

括号的闭合规则 = 栈的 "后进先出" 规则

后遇到的左括号，必须最先被闭合。 比如([)]：

• 先遇到(，再遇到[
• 接下来遇到)，应该先闭合最后遇到的[，但这里闭合了(，所以错误

栈正好完美匹配这个逻辑：

• 遇到左括号 → 压入栈顶（后遇到的在最上面）
• 遇到右括号 → 弹出栈顶的左括号，检查是否匹配。

完整解题步骤

1. 边界预判：如果字符串长度是奇数，直接返回false（括号必须成对出现）
2. 建立映射：用哈希表存储 "右括号 → 对应左括号" 的映射，方便快速查找
3. 遍历字符串：
   • 遇到左括号 → 压入栈
   • 遇到右括号：
     • 如果栈为空（没有对应的左括号）→ 返回false
     • 如果栈顶的左括号和当前右括号不匹配 → 返回false
     • 如果匹配 → 弹出栈顶
4. 最终检查：遍历结束后，如果栈为空，说明所有左括号都匹配成功；否则有剩余左括号没匹配，返回false

class Solution { public: bool isValid(string s) { int n = s.size(); //如果是奇数肯定不成对 直接返回false if(n%2 == 1){ return false; } //哈希表维护正常的配对 //右括号当键 unordered_map<char,char> pairs = { {')','('}, {']','['}, {'}','{'} }; stack<char> stk; //遍历这个s 遇到左括号就入栈 遇到右括号就和栈顶匹配 for(char ch:s){ if(pairs.count(ch)){//判断ch这个键存不存在 也就是是不是右括号 //如果哈希表里有ch当前这个字符 //如果当前栈为空（那就没有匹配的） 或者栈顶不等于当前元素的另一半 if(stk.empty()||stk.top()!= pairs[ch]){ return false; } //否则就是匹配上了 那就弹出栈顶 stk.pop(); } else{//如果不是右括号 那就入栈 stk.push(ch);} } return stk.empty(); //最后看看最后的栈是否为空 如果是空说明都匹配了 所以是真的；如果不为空 说明有剩余 说明假的 } };