LeetCode刷题笔记-20-有效的括号 2026.04.15 算法蒟蒻的成长记录，LeetCode

LeetCode 刷题笔记：20. 有效的括号

核心思路是用 栈 进行括号匹配。

一个核心的技巧:

当遇到左括号时，直接把它对应的右括号压入栈；遇到右括号时，直接与栈顶比较。

这样可以避免每次都去“成对取出后再比较”，代码更简洁。

---

思路

遍历字符串 s：

• 遇到 ( 则压入 )。
• 遇到 [ 则压入 ]。
• 遇到 { 则压入 }。
• 遇到其他字符时，检查当前栈是否为空，或栈顶字符是否与当前字符不匹配。
  • 若不匹配，则说明括号顺序错误或种类不一致。
  • 若匹配，则弹出栈顶，继续判断下一个字符。

最终要求栈为空，说明所有括号都已配对。

---

关键技巧

• 采用“压入预期右括号”的技巧，省去了额外的映射判断。
• 先判断字符串长度是否为奇数，如果是则直接返回 false。
• 还要判断栈是否为空，以避免 st.top() 在空栈上调用。

---

C++ 代码

class Solution {
public:
    bool isValid(const string& s) {
        int n = s.size();
        if (n % 2 != 0) return false;

        stack<char> st;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '[') st.push(']');
            else if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (st.empty() || s[i] != st.top()) return false;
            else st.pop();
        }
        return st.empty();
    }
};

---

易错点

• 直接把 st.empty() 写反会把合法字符串误判为错误。
• 不检查栈空而直接调用 st.top() 会导致未定义行为。
• 空字符串 "" 应该返回 true，因为它是有效的括号序列。

---

总结

这题的难点不在算法本身，而在边界条件和判断逻辑是否严谨。
用“将预期右括号压入栈”的变形方法，代码既简单又高效，适合处理这类括号匹配题。
只要保证“栈空检查 + 栈顶匹配 + 最终栈空”，就能正确解决题目。