有效的括号 图解题解

这道题到底在问什么

s

"([])"

输出

true

最优解：一步一步想明白

1. 3遇到左括号就压进栈；遇到右括号，就看栈顶的左括号能不能和它配成一对——能配就弹出栈顶，不能配就说明不合法。
2. 4栈为空上面是要处理的字符串，下面是我们的栈。开始逐个字符处理。
3. 5左括号 → 入栈'(' 是左括号，压入栈。栈：[ ( ]
4. 6左括号 → 入栈'[' 也是左括号，压入栈。栈：[ (, [ ]，栈顶是 '['。
5. 7右括号 vs 栈顶 '['']' 是右括号。看栈顶是 '['，正好是一对！可以把栈顶弹出去。
6. 8弹出 '['配对成功，弹出栈顶 '['。栈剩下：[ ( ]。
7. 9右括号 vs 栈顶 '('')' 是右括号。栈顶是 '('，又是一对！弹出。
8. 10弹出 '('弹出 '('，栈又空了。
9. 11栈空 → 合法字符串走完，栈正好空了——说明每个左括号都找到了对应的右括号，返回 true。
10. 12两种情况：① 右括号来了但栈顶配不上；② 字符串结束时栈还没空（有左括号没人配）。来看个反例。
11. 13入栈处理 "(]"：先把 '(' 压入栈。
12. 14栈顶 '(' 配不上 ']'遇到 ']'，可栈顶是 '('，对不上号——立刻返回 false。
13. 15只有一种括号时，确实可以用一个计数器：左加一、右减一，全程不为负、最后归零就合法。但一旦有多种括号、还能交叉，比如 "([)]"，光数个数就废了——来看这个最坑的例子。
14. 16左括号 → 入栈先读第 0 个 '('，是左括号，压入栈。栈：[ ( ]。
15. 17左括号 → 入栈，栈：[ (, [ ]再读第 1 个 '['，也是左括号，入栈。两个左括号都进来了。注意：要是只用计数器，此刻「左括号 = 2」，看不出谁套谁。
16. 18栈顶是 '['，配不上 ')'读到 ')'，它该配 '('；可最近的那个左括号是 '['——顺序乱了，返回 false。计数器只会说「左 2 右 1，还没数完」，根本发现不了这个交叉错误。栈记住了「最近的左括号是谁」，这正是计数器给不了的。
17. 21凡是「最近出现的要最先被匹配/抵消」的问题，都该想到栈：逆波兰表达式、字符串解码、消消乐式的相邻消除……
18. 27① 为什么用栈不用计数器？——只有一种括号能计数，但 "([)]" 这种多类型交叉必须靠栈记住「最近的左括号是谁」。② 能提前剪枝吗？——能：长度是奇数直接 false；右括号配不上立即 return。③ 为什么结束还要判栈空？——像 "(" 这种走完栈里还剩没配对的左括号，要返回 false。
19. 28「栈 = 最近的先处理」是一整类题的内核：LC394 字符串解码（遇到 ] 弹出最近一段重复）、LC1047 相邻消除，再进阶到 LC739 / LC42 的单调栈（遇到更大的就回头结算）。学会这一道，栈这一类就入门了——更多在 栈专题 继续，或让小欧私教陪你把这套骨架套到下一题。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def isValid(self, s):
        stack = []
        pairs = {')': '(', ']': '[', '}': '{'}
        for ch in s:
            if ch in pairs:                 # 右括号
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:
                stack.append(ch)            # 左括号入栈
        return not stack                   # 栈空才合法

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char,char> p = {{')','('},{']','['},{'}','{'}};
        for (char ch : s) {
            if (p.count(ch)) {              // 右括号
                if (st.empty() || st.top() != p[ch]) return false;
                st.pop();
            } else st.push(ch);            // 左括号入栈
        }
        return st.empty();
    }
};

class Solution {
    public boolean isValid(String s) {
        Deque<Character> st = new ArrayDeque<>();
        Map<Character,Character> p = new HashMap<>();
        p.put(')','('); p.put(']','['); p.put('}','{');
        for (char ch : s.toCharArray()) {
            if (p.containsKey(ch)) {        // 右括号
                if (st.isEmpty() || !st.pop().equals(p.get(ch))) return false;
            } else st.push(ch);            // 左括号入栈
        }
        return st.isEmpty();
    }
}

# 凡是「相邻可抵消 / 最近优先匹配」都套这个骨架
stack = []
for x in 序列:
    if 该入栈(x):              # 把 x 留着等以后配
        stack.append(x)
    elif stack and 能抵消(stack[-1], x):  # 和栈顶抵消
        stack.pop()           # 抵消就弹掉
    else:
        失败处理()             # 栈空/对不上 → 视题 return 或 push x
return 收尾(stack)            # 本题=要求栈空；别的题=返回栈内剩余

// 凡是「相邻可抵消 / 最近优先匹配」都套这个骨架
stack<T> st;
for (auto& x : 序列) {
    if (该入栈(x)) st.push(x);                 // 留着等以后配
    else if (!st.empty() && 能抵消(st.top(), x))
        st.pop();                             // 抵消就弹掉
    else 失败处理();                           // 栈空/对不上
}
return 收尾(st);                              // 本题=要求 st.empty()

// 凡是「相邻可抵消 / 最近优先匹配」都套这个骨架
Deque<T> st = new ArrayDeque<>();
for (T x : 序列) {
    if (该入栈(x)) st.push(x);                 // 留着等以后配
    else if (!st.isEmpty() && 能抵消(st.peek(), x))
        st.pop();                             // 抵消就弹掉
    else 失败处理();                           // 栈空/对不上
}
return 收尾(st);                              // 本题=要求 st.isEmpty()

复杂度

面试官可能追问