1. 题目描述

简单
字符串
栈

给定一个只包含 (、)、[、]、{、} 的字符串 s，判断字符串中的括号是否有效。

有效括号需要同时满足两点：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须按照正确顺序闭合。

示例 1

输入：s = “()[]{}” 输出：true 解释：三组括号都能正确匹配。

示例 2

输入：s = “([)]” 输出：false 解释：虽然括号数量对得上，但闭合顺序不正确。

2. 核心算法思维：栈（Stack）

我当时的写题思路

写这题时的思路比较直接，先不追求最短代码，而是先把括号匹配过程拆清楚：

1. 遍历字符串，遇到左括号就先入栈。
2. 遇到右括号时，先判断栈是不是空的。
3. 如果栈为空，说明这个右括号找不到对应的左括号，直接返回 false。
4. 如果栈不为空，就取出栈顶元素，分别判断是不是 ()、[]、{} 这三种合法配对。
5. 如果能配对，就把栈顶弹出；如果不能配对，就说明顺序或类型错了，直接返回 false。
6. 整个字符串遍历结束后，再检查栈是否为空。为空说明全部匹配成功，否则说明还有左括号没被关掉。

这种写法的优点是思路顺、调试也方便，尤其适合作为“栈”这类题目的入门写法。

3. 按照我当前思路的实现（C++）

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for (char ch : s) {
            if (ch == '(' || ch == '[' || ch == '{') {
                st.push(ch);
                continue;
            }

            if (st.empty()) {
                return false;
            }

            char top = st.top();
            if (top == '(' && ch == ')') {
                st.pop();
            } else if (top == '[' && ch == ']') {
                st.pop();
            } else if (top == '{' && ch == '}') {
                st.pop();
            } else {
                return false;
            }
        }

        return st.empty();
    }
};

这段代码和我实际写题时的思路是一一对应的：先把左括号压栈，再判断当前右括号能不能和栈顶匹配。它不是最花哨的写法，但逻辑非常直观。

4. 如果想写得更简洁：更好的方法

这样做的好处有两个：

• 判断逻辑更短，不需要反复写三组配对分支。
• 栈顶语义更清楚，表示“当前最期待看到的右括号”。

另外还可以加一个小优化：如果字符串长度是奇数，可以直接返回 false。因为有效括号一定是成对出现的。

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) {
            return false;
        }

        stack<char> st;
        for (char ch : s) {
            if (ch == '(') {
                st.push(')');
            } else if (ch == '[') {
                st.push(']');
            } else if (ch == '{') {
                st.push('}');
            } else {
                if (st.empty() || st.top() != ch) {
                    return false;
                }
                st.pop();
            }
        }

        return st.empty();
    }
};

5. 复杂度分析

无论是当前的写法，还是上面这个更简洁的写法，复杂度其实都一样：

• 时间复杂度：O(n)
• 每个字符最多入栈一次、出栈一次，整体只遍历字符串一遍。
• 空间复杂度：O(n)
• 最坏情况下，字符串全是左括号，需要把它们全部压入栈中。

6. 易错点与避坑指南

7. 互动与补充资料

这道题很适合作为“栈”的入门题。它的重点不是死记模板，而是建立一种判断习惯：

当题目要求你维护“最近一个还没处理完的状态”时，就可以优先想想栈是不是合适的数据结构。

本题的代码已同步至我的个人 GitHub 仓库。