LeetCode 20｜有效的括号：从暴力枚举到栈的五种解法 | 星雨笔录

一、题目描述

题目： LeetCode 20. 有效的括号　难度： 简单　知识点： 字符串、模拟、栈（Stack）

给定一个字符串 s，其中只包含 (、)、[、]、{、} 六种字符，判断这个字符串是否有效。

有效字符串必须同时满足：

1. 类型正确： ( 只能由 ) 闭合，[ 只能由 ] 闭合，{ 只能由 } 闭合。
2. 顺序正确： 内层括号必须先闭合，外层括号才能闭合，不能交叉配对。
3. 完全匹配： 不能有多余的右括号，也不能留下未闭合的左括号。

输入： 字符串 s，1 ≤ s.length ≤ 10⁴，并且只包含以上六种括号。

输出： 布尔值；有效返回 true，否则返回 false。

例如，"([])" 合法，因为 [] 先闭合，外层的 () 再闭合；"([)]" 不合法，虽然三种括号中 () 与 [] 的数量都相等，但 ) 出现时，最近一个尚未闭合的是 [，顺序被破坏了。

本题最关键的限制是：不能只检查数量，还要检查配对类型和嵌套顺序。

二、测试用例

编写算法前，先明确怎样判断程序是否正确。测试分为黑盒测试和白盒测试：前者只看输入与输出，后者还要检查代码中的关键判断和执行路径是否被覆盖。

2.1 黑盒测试：根据题目规则设计输入与输出

黑盒测试不关心程序使用栈、数组还是字符串替换，只根据需求划分有效等价类、无效等价类以及边界值。下表的用例适用于后面的全部五种解法。

编号	测试目的	输入s	预期输出	原因
B01	最短合法圆括号	"()"	true	正确配对
B02	最短合法方括号	"[]"	true	正确配对
B03	最短合法花括号	"{}"	true	正确配对
B04	并列不同类型	"()[]{}"	true	三对分别闭合
B05	多层嵌套	"{[()]}"	true	由内向外闭合
B06	复杂合法嵌套	"([{}])"	true	多类型嵌套顺序正确
B07	同类嵌套	"((()))"	true	多层圆括号逐级闭合
B08	相邻与嵌套混合	"([]){}"	true	两种结构混合
B09	配对类型错误	"(]"	false	左右类型不相同
B10	交叉嵌套	"([)]"	false	数量正确但闭合顺序错误
B11	第一个字符是右括号	")("	false	无左括号可供配对
B12	中途出现多余右括号	"())("	false	匹配完成后又出现)
B13	末尾仍有未闭合括号	"(("	false	两个左括号都没有闭合
B14	只有右括号	"))"	false	没有左括号
B15	最短奇数输入	"("	false	长度为 1，不可能成对
B16	奇数且类型混合	"[]]"	false	多余一个右括号
B17	相同数量但顺序颠倒	"]["	false	右括号先于左括号
B18	无法消除的交错结构	"[(])"	false	括号交叉
B19	最大长度、深度嵌套	"("重复 5000 次，再")"重复 5000 次	true	长度 10000、嵌套深度 5000
B20	最大长度、左括号未闭合	"("重复 10000 次	false	所有括号都没有闭合
B21	最大长度、立即冲突	")"重复 10000 次	false	第一个字符就不合法
B22	最大长度、类型不符	"("重复 5000 次，再"]"重复 5000 次	false	首次闭合就类型冲突

输入范围说明： 题目规定字符串长度至少为 1，所以空字符串不属于官方测试范围。可以额外检验 s = ""：下文五种实现都会返回 true，表示空串没有不匹配的括号；这只是扩展约定，不能把它当作题目强制要求。

2.2 白盒测试：检查算法里的关键分支

黑盒测试能验证结果，却未必能证明每个分支都执行过。白盒测试要提前指出：哪个条件需要触发、用什么输入触发、应该走哪条路径。

关注的执行路径	代表用例	要观察的现象
奇数长度的提前返回	B15："("	不必进入主循环，直接返回false
普通左括号入栈	B05："{[()]}"	先依次保存尚未闭合的括号
三种括号类型的成功配对	B04："()[]{}"	()、[]、{}三个判断都能通过
栈为空时遇到右括号	B17："]["	不能执行pop，直接返回false
栈非空但类型不匹配	B09："(]"	取出的括号类型与当前字符冲突
已经匹配成功，后面又出现右括号	B12："())("	不能因为前面出现合法括号就提前返回true
扫描结束但栈不为空	B13："(("	不能只看循环中是否出错
多层嵌套导致反复消除	B05："{[()]}"	删除内层后必须重新查找外层配对
一轮消除后字符串完全没变化	B10："([)]"	退出消除循环，残余非空则失败
数组栈top加减与边界	B05、B17、B13	验证入栈、出栈、空栈及最终剩余状态
映射规则查找成功与失败	B04、B05	分别走到右括号查表和左括号入栈分支

这里列出的是应覆盖的测试路径，不是声称已经通过工具测得 100% 分支覆盖率。由于五种代码的条件分支存在差异，测试时应对照各自的实现逐项核查。

2.3 大规模与组合测试

只测试表中的二十几个输入还不够。还可以采用两种补充办法：

• 穷举短串： 对长度 1 到 6 的六种括号进行全排列，生成全部 6¹ + 6² + … + 6⁶ = 55986 个字符串，让五种方法的结果相互比较；如果结果不一致，输出导致差异的输入。（相互比较有助于发现问题，但不能单独证明所有结果正确。）
• 构造合法串再变形： 如果 A、B 有效，那么 AB、(A)、[A]、{A} 都有效；也可以故意删除、交换或替换某个字符，检查输出是否符合改变后的实际配对规则。注意修改一个字符不一定让字符串无效，因此每个变形后的预期结果仍需核对。

接下来按“先做出正确结果，再逐步减少重复工作、改进代码表达和工程适应性”的思路研究五种写法。

三、解法一：暴力枚举与消除——先用最直观的办法做出来

3.1 核心思想

拿到 "{[()]}"，先不考虑任何数据结构。人眼最容易发现的是中间的 ()：这两个字符挨在一起，肯定构成有效的一对。把它们删掉，原字符串变成 "{[]}"；再删掉 []，得到 "{}"；最后删掉 {}，字符串变为空。

{[()]}  →  {[]}  →  {}  →  ""

反过来，如果是 "([)]"，无论怎样检查，都找不到相邻的 ()、[] 或 {}，也就无法继续消除，最后剩下非空字符串，因此无效。

于是可以先得到一个完全直接的判断办法：反复查找并删除紧挨着的合法括号对，直到没有括号可以删除；若剩余字符串为空，则原字符串有效。

为什么这成立？有效的非空括号字符串一定存在一对“最内层”的相邻括号；删除这对不会改变其他括号的配对关系。一直删除下去，合法串可以化为空串；如果删不动时还有字符，说明存在无法匹配的结构。

3.2 执行步骤

1. 读取字符串长度。如果长度是奇数，直接返回 false，因为每对括号都需要两个字符。
2. 保存一份当前待处理的字符串。后续删除操作只修改这份字符串；在 C 等允许原地修改的语言中，最好先复制输入，避免改变调用者的数据。
3. 从左到右枚举相邻的两个字符，寻找三种合法组合：()、[]、{}。只有这三种组合能够直接删除，例如 (] 和 [) 都不能删除。
4. 如果发现合法组合，删除它，使右侧字符向左靠拢。可以一次只删除一对，也可以在一次处理中删除多对；关键是只删除真正相邻且类型匹配的组合。
5. 删除后再次查找，因为原来隔开的字符可能刚刚变成一对。例如 "([])" 先删掉 [] 才会出现新的 ()。
6. 当一轮检查中没有删除任何字符时停止。如果此时字符串长度为 0，返回 true；否则返回 false。

完整推演： "([]){}" → "(){}" → "{}" → ""，结果是 true。而 "(]" 没有任何可删除的相邻组合，第一轮便停止，结果是 false。

3.3 代码实现

下面五份代码都是同一种消除规则，但一次删除的数量可能不同：C 实现每轮删一对，其他实现允许连续删除若干对。两者均会重复检查直到无法继续删除。

::: code-group C|C++|Java|Python|JavaScript

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static bool isPair(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

bool isValid(char *s) {
    size_t n = strlen(s);
    // 先过滤奇数长度，减少不必要的字符串处理。
    if (n % 2 != 0) return false;
    // 复制输入到可修改的缓冲区，避免修改传入的原字符串。
    char *buf = malloc(n + 1);
    if (buf == NULL) return false;
    memcpy(buf, s, n + 1);

    // 不断重复消除，直到这一轮再也找不到合法相邻括号对。
    while (true) {
        bool removed = false;
        // 查找能直接配对的相邻字符，如 ()、[]、{}。
        for (size_t i = 0; i + 1 < n; ++i) {
            // 找到第一对相邻合法括号，马上删除。
            if (isPair(buf[i], buf[i + 1])) {
                // 包括末尾 '\0' 一并左移。
                // 把后面的字符整体左移两格，同时保留结尾字符串终止符。
                memmove(buf + i, buf + i + 2, n - i - 1);
                n -= 2;
                removed = true;
                break;
            }
        }
        // 这一轮没有任何变化时停止；若还有残余字符就是无效。
        if (!removed) break;
    }

    // 只有所有括号对都能消除，最终字符串才会变为空。
    bool ok = (n == 0);
    free(buf);
    return ok;
}

#include <string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        // 先过滤奇数长度，减少不必要的字符串处理。
        if (s.size() % 2 != 0) return false;
        // 不断重复消除，直到这一轮再也找不到合法相邻括号对。
        while (true) {
            bool changed = false;
            // 查找能直接配对的相邻字符，如 ()、[]、{}。
            for (const string pair : {"()", "[]", "{}"}) {
                size_t pos;
                while ((pos = s.find(pair)) != string::npos) {
                    // 从当前字符串里移除找到的两个字符。
                    s.erase(pos, 2);
                    changed = true;
                }
            }
            // 这一轮没有任何变化时停止；若还有残余字符就是无效。
            if (!changed) break;
        }
        // 只有所有括号对都能消除，最终字符串才会变为空。
        return s.empty();
    }
};

class Solution {
    public boolean isValid(String s) {
        // 先过滤奇数长度，减少不必要的字符串处理。
        if (s.length() % 2 != 0) return false;
        // 不断重复消除，直到这一轮再也找不到合法相邻括号对。
        while (true) {
            // 尝试删除三种括号对，得到变短后的新字符串。
            String next = s.replace("()", "")
                           .replace("[]", "")
                           .replace("{}", "");
            // 这一轮没有任何变化时停止；若还有残余字符就是无效。
            if (next.equals(s)) return s.isEmpty();
            s = next;
        }
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        # 先过滤奇数长度，减少不必要的字符串处理。
        if len(s) % 2 != 0:
            return False
        # 不断重复消除，直到这一轮再也找不到合法相邻括号对。
        while True:
            # 尝试删除三种括号对，得到变短后的新字符串。
            next_s = s.replace('()', '').replace('[]', '').replace('{}', '')
            # 这一轮没有任何变化时停止；若还有残余字符就是无效。
            if next_s == s:
                # 只有所有括号对都能消除，最终字符串才会变为空。
                return not s
            s = next_s

var isValid = function(s) {
    // 先过滤奇数长度，减少不必要的字符串处理。
    if (s.length % 2 !== 0) return false;
    // 不断重复消除，直到这一轮再也找不到合法相邻括号对。
    while (true) {
        // 尝试删除三种括号对，得到变短后的新字符串。
        const next = s.replaceAll('()', '')
                      .replaceAll('[]', '')
                      .replaceAll('{}', '');
        // 这一轮没有任何变化时停止；若还有残余字符就是无效。
        if (next === s) return s.length === 0;
        s = next;
    }
};

:::

3.4 复杂度分析

设字符串长度为 n。

• 时间复杂度：最坏 O(n²)。 每次扫描、查找或删除可能处理 O(n) 个字符；最坏情况下最多会进行 n/2 次有效消除。例如高度嵌套的字符串，外层括号往往要等内层先删除后才能配对。
• 辅助空间复杂度：O(n) 上界。 C 版先复制输入；Java、Python、JavaScript 的字符串替换会构造新字符串；C++ 在删除过程中也可能产生临时字符串。具体实现的峰值内存因语言而异，但都可以用线性上界描述。

问题出在哪里？ 我们反复扫描字符串，是为了不断找到“刚刚形成的相邻括号”。如果能在第一次读取字符时就记住哪些左括号还没闭合，也许根本不用反复扫描。这个发现自然引出栈。

四、解法二：标准栈——把平方级扫描优化成一次遍历

4.1 核心思想

仔细看 "{[()]}" 的匹配顺序：最后出现的左括号 ( 最先被 ) 闭合；其次才是 [、{。也就是说，后出现、尚未闭合的左括号，必须先匹配。

这种顺序叫后进先出（LIFO，Last In, First Out），恰好就是栈（Stack）的规则。栈只允许从栈顶放入元素（push），也从栈顶取走元素（pop）。

因此，不再反复删除字符串，而是从左往右只扫描一次，用栈保存尚未匹配的左括号。遇到右括号，就检查它能否闭合栈顶最近的左括号。

4.2 执行步骤

1. 判断字符串长度是否为奇数；若是，返回 false。
2. 创建一个空栈。规定：栈里每一个元素都是已经读到、但尚未匹配的左括号。
3. 从左到右读取一个字符 c。如果 c 是 (、[ 或 {，直接入栈；因为现在只有左括号，暂时无法判断它何时闭合。
4. 如果 c 是右括号，先检查栈是否为空。若栈为空，说明右括号出现在任何可匹配的左括号之前，立即返回 false，绝不能先执行 pop。
5. 栈非空时取出栈顶左括号，分别检查三种合法组合：()、[]、{}。若类型不同，例如栈顶是 [ 却读到 )，立即返回 false。
6. 如果匹配成功，就继续读取下一个字符。不要因为成功匹配一对括号就返回 true，后面还可能出现额外的右括号。
7. 全部字符读完后检查栈：栈为空，说明每个左括号都被正确闭合，返回 true；栈不为空，说明还有未闭合的左括号，返回 false。

用 "([)]" 推演一次，栈从左到右表示“栈底 → 栈顶”：

当前字符	动作	剩余栈	结果
(	左括号入栈	(	继续
[	左括号入栈	( [	继续
)	弹出[，发现与)类型不同	(	false，停止

关键不在于 () 与 [] 有没有各出现一次，而在于当前右括号是否对应最近的那个未完成左括号。这就是栈比数量统计更合适的原因。

4.3 代码实现

注意这里保存的是原始左括号。Java 示例沿用现代 Java 推荐的 ArrayDeque，而不是历史遗留的 Stack 类；Deque 的 push / pop 操作同样可以实现栈。

::: code-group C|C++|Java|Python|JavaScript

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool isValid(char *s) {
    size_t n = strlen(s);
    // 括号必须成对出现；奇数长度不可能完全匹配。
    if (n % 2 != 0) return false;

    // 建立空栈，存储仍需要匹配的字符。
    char *stack = malloc(n + 1);
    if (stack == NULL) return false;
    size_t top = 0;

    // 从左到右扫描，每次只处理一个括号。
    for (size_t i = 0; i < n; ++i) {
        char c = s[i];
        // 左括号直接入栈，等待未来对应的右括号。
        if (c == '(' || c == '[' || c == '{') {
            stack[top++] = c;
        } else {
            // 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
            if (top == 0) {
                free(stack);
                return false;
            }
            // 取出最近一个未闭合的左括号，准备核对类型。
            char left = stack[--top];
            // 只有 ()、[]、{} 三种组合合法，其他组合一律失败。
            if (!((left == '(' && c == ')') ||
                  (left == '[' && c == ']') ||
                  (left == '{' && c == '}'))) {
                free(stack);
                return false;
            }
        }
    }

    // 处理完所有字符后，只有没有遗留待匹配字符才有效。
    bool ok = (top == 0);
    free(stack);
    return ok;
}

#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        // 括号必须成对出现；奇数长度不可能完全匹配。
        if (s.size() % 2 != 0) return false;
        // 建立空栈，存储仍需要匹配的字符。
        stack<char> st;

        // 从左到右扫描，每次只处理一个括号。
        for (char c : s) {
            // 左括号直接入栈，等待未来对应的右括号。
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                // 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
                if (st.empty()) return false;
                // 取出最近一个未闭合的左括号，准备核对类型。
                char left = st.top();
                st.pop();
                // 只有 ()、[]、{} 三种组合合法，其他组合一律失败。
                if (!((left == '(' && c == ')') ||
                      (left == '[' && c == ']') ||
                      (left == '{' && c == '}'))) return false;
            }
        }
        // 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return st.empty();
    }
};

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        // 括号必须成对出现；奇数长度不可能完全匹配。
        if (s.length() % 2 != 0) return false;
        // 建立空栈，存储仍需要匹配的字符。
        Stack<Character> stack = new Stack<>();

        // 从左到右扫描，每次只处理一个括号。
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 左括号直接入栈，等待未来对应的右括号。
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                // 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
                if (stack.isEmpty()) return false;
                // 取出最近一个未闭合的左括号，准备核对类型。
                char left = stack.pop();
                // 只有 ()、[]、{} 三种组合合法，其他组合一律失败。
                if (!((left == '(' && c == ')') ||
                      (left == '[' && c == ']') ||
                      (left == '{' && c == '}'))) return false;
            }
        }
        // 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return stack.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        # 括号必须成对出现；奇数长度不可能完全匹配。
        if len(s) % 2 != 0:
            return False
        # 建立空栈，存储仍需要匹配的字符。
        stack = []
        # 从左到右扫描，每次只处理一个括号。
        for c in s:
            # 左括号直接入栈，等待未来对应的右括号。
            if c in "([{":
                stack.append(c)
            else:
                # 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
                if not stack:
                    return False
                # 取出最近一个未闭合的左括号，准备核对类型。
                left = stack.pop()
                # 只有 ()、[]、{} 三种组合合法，其他组合一律失败。
                if not ((left == '(' and c == ')') or
                        (left == '[' and c == ']') or
                        (left == '{' and c == '}')):
                    return False
        # 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return not stack

var isValid = function(s) {
    // 括号必须成对出现；奇数长度不可能完全匹配。
    if (s.length % 2 !== 0) return false;
    // 建立空栈，存储仍需要匹配的字符。
    const stack = [];

    // 从左到右扫描，每次只处理一个括号。
    for (const c of s) {
        // 左括号直接入栈，等待未来对应的右括号。
        if (c === '(' || c === '[' || c === '{') {
            stack.push(c);
        } else {
            // 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
            if (stack.length === 0) return false;
            // 取出最近一个未闭合的左括号，准备核对类型。
            const left = stack.pop();
            // 只有 ()、[]、{} 三种组合合法，其他组合一律失败。
            if (!((left === '(' && c === ')') ||
                  (left === '[' && c === ']') ||
                  (left === '{' && c === '}'))) return false;
        }
    }
    // 处理完所有字符后，只有没有遗留待匹配字符才有效。
    return stack.length === 0;
};

:::

4.4 复杂度分析

• 时间复杂度：O(n)。 每个字符读取一次。左括号最多入栈一次，成功匹配时最多出栈一次，单次栈操作为常数时间。
• 辅助空间复杂度：最坏 O(n)。 当字符串前半部分全是左括号时，需要暂存大量待匹配元素。若同时最多有 d 个左括号未闭合，动态栈实际所需元素数量为 O(d)，最坏 d = O(n)。

优化发生在哪里？ 暴力法删除内层括号后可能再次扫描剩余字符串；栈法把未闭合状态直接存起来，省去了反复寻找和移动字符的工作，最坏时间从 O(n²) 降到 O(n)。

五、解法三：提前保存右括号——把匹配判断简化为一次比较

5.1 核心思想

标准栈法在读到 ) 时，会先从栈顶拿出一个左括号，再判断它是不是 (。其实，我们可以在左括号入栈时就把它改成“未来应该看到什么”：

当前读到的左括号	存入栈中的字符	意思
(	)	等待一个)
[	]	等待一个]
{	}	等待一个}

栈仍然遵守后进先出，只是里面存的不再是“已经出现的左括号”，而是“尚未出现、但下一步应该匹配的右括号”。这样一来，读到真正的右括号时，只需比较它和栈顶字符是否相同。

5.2 执行步骤

1. 如果字符串长度为奇数，返回 false。
2. 创建空栈，规定栈中存放的是期待出现的右括号。
3. 从左到右读取字符 c。若 c 为 (，则把 ) 入栈；若为 [，把 ] 入栈；若为 {，把 } 入栈。
4. 若 c 已经是右括号，先检查栈是否为空。空栈意味着没有正在等待它的左括号，返回 false。
5. 若栈不为空，弹出栈顶期待字符 expected，检查它是否等于 c。不相同就返回 false；相同才继续。
6. 扫描全部结束后，只有栈为空才能返回 true。只要还有期待字符没有出现，就说明至少有一对没有闭合。

例子： 读取 "([])"：

当前字符	处理动作	栈内期待的右括号（底 → 顶）
(	保存将来需要的)	)
[	保存将来需要的]	) ]
]	与栈顶]相同，弹出	)
)	与栈顶)相同，弹出	空
结束	栈为空	返回true

相较标准栈，改变的只是保存的信息，不是匹配顺序。不要误认为这种写法的渐进复杂度更低。

5.3 代码实现

留意 stack.pop() != c 这样的写法：在比较之前，必须保证栈非空，否则会发生无效出栈；代码中使用 || 的短路特性保障这一点。

::: code-group C|C++|Java|Python|JavaScript

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool isValid(char *s) {
    size_t n = strlen(s);
    // 括号必须成对出现；奇数长度不可能完全匹配。
    if (n % 2 != 0) return false;
    // 建立空栈，只保存「期望将来出现的右括号」。
    char *stack = malloc(n + 1);
    if (stack == NULL) return false;
    size_t top = 0;

    // 从左到右扫描，每次只处理一个括号。
    for (size_t i = 0; i < n; ++i) {
        char c = s[i];
        // 左括号不入栈本身，而是存入它期待的右括号。
        if (c == '(') stack[top++] = ')';
        else if (c == '[') stack[top++] = ']';
        else if (c == '{') stack[top++] = '}';
        // 空栈直接失败；否则取出栈顶期待字符，和当前字符比较。
        else if (top == 0 || stack[--top] != c) {
            free(stack);
            return false;
        }
    }

    // 处理完所有字符后，只有没有遗留待匹配字符才有效。
    bool ok = (top == 0);
    free(stack);
    return ok;
}

#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        // 括号必须成对出现；奇数长度不可能完全匹配。
        if (s.size() % 2 != 0) return false;
        // 建立空栈，只保存「期望将来出现的右括号」。
        stack<char> st;
        // 从左到右扫描，每次只处理一个括号。
        for (char c : s) {
            // 左括号不入栈本身，而是存入它期待的右括号。
            if (c == '(') st.push(')');
            else if (c == '[') st.push(']');
            else if (c == '{') st.push('}');
            else {
                // 先判断是否为空，再取出栈顶进行严格比较。
                if (st.empty() || st.top() != c) return false;
                st.pop();
            }
        }
        // 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return st.empty();
    }
};

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValid(String s) {
        // 括号必须成对出现；奇数长度不可能完全匹配。
        if (s.length() % 2 != 0) return false;
        // 建立空栈，只保存「期望将来出现的右括号」。
        Deque<Character> stack = new ArrayDeque<>();
        // 从左到右扫描，每次只处理一个括号。
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 左括号不入栈本身，而是存入它期待的右括号。
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            // 空栈直接失败；否则取出栈顶期待字符，和当前字符比较。
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        // 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return stack.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        # 括号必须成对出现；奇数长度不可能完全匹配。
        if len(s) % 2 != 0:
            return False
        # 建立空栈，只保存「期望将来出现的右括号」。
        stack = []
        # 从左到右扫描，每次只处理一个括号。
        for c in s:
            # 左括号不入栈本身，而是存入它期待的右括号。
            if c == '(':
                stack.append(')')
            elif c == '[':
                stack.append(']')
            elif c == '{':
                stack.append('}')
            # 空栈直接失败；否则取出栈顶期待字符，和当前字符比较。
            elif not stack or stack.pop() != c:
                return False
        # 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return not stack

var isValid = function(s) {
    // 括号必须成对出现；奇数长度不可能完全匹配。
    if (s.length % 2 !== 0) return false;
    // 建立空栈，只保存「期望将来出现的右括号」。
    const stack = [];
    // 从左到右扫描，每次只处理一个括号。
    for (const c of s) {
        // 左括号不入栈本身，而是存入它期待的右括号。
        if (c === '(') stack.push(')');
        else if (c === '[') stack.push(']');
        else if (c === '{') stack.push('}');
        // 空栈直接失败；否则取出栈顶期待字符，和当前字符比较。
        else if (stack.length === 0 || stack.pop() !== c) return false;
    }
    // 处理完所有字符后，只有没有遗留待匹配字符才有效。
    return stack.length === 0;
};

:::

5.4 复杂度分析

• 时间复杂度：O(n)。 每个字符最多触发一次入栈或者出栈操作。
• 辅助空间复杂度：最坏 O(n)。 最多保存 O(n) 个等待闭合的右括号。

这一轮的优化是什么？ 不再每次从栈顶取到左括号后检查三种组合，而是提前记录其对应右括号，将配对判断收敛为一次相等性比较。这是代码逻辑与常数因子的简化，不是复杂度数量级的改变。

六、解法四：映射表 + 双端队列——把配对规则独立出来

6.1 核心思想

前面通过 if / else 判断三种括号配对。对于题目限定的三种括号完全够用，但如果在编辑器、解释器或配置解析器中，需要把不同定界符的匹配规则集中管理，一张**映射表（Map）**会更清晰。

右括号 → 对应左括号
   )   →    (
   ]   →    [
   }   →    {

这里将两项职责分开：栈负责匹配顺序，映射表负责匹配类型。栈里仍保存尚未闭合的左括号。

Java 中，Deque 是双端队列接口，ArrayDeque 是常见实现，可以用 push / pop 当作栈。Map<Character, Character> 保存 ')' → '(' 等关系。由于题目只有三条规则，映射表属于常数规模。

6.2 执行步骤

1. 判断字符串长度；奇数时直接返回 false。
2. 建立映射表：右括号 ) 对应 (，] 对应 [，} 对应 {。
3. 创建空栈，用于保存所有已经读到但还没匹配的左括号。
4. 从左到右读取当前字符 c，先判断它是否存在于映射表的键中。
5. 如果 c 不在映射表的键中，按照本题输入只包含六种括号的规定，它一定是左括号，于是将它入栈。（真实工程中若可能有其他字符，应单独验证或定义忽略规则。）
6. 如果 c 是右括号，先确认栈非空；若为空，立即返回 false。
7. 栈非空时，通过映射表查出 c 应该对应哪个左括号，再与栈顶最近的左括号比较；若不同，返回 false；否则取走这个左括号并继续。
8. 遍历完毕时，栈为空才返回 true，否则返回 false。

例如读取 "{[]}"：先将 {、[ 依次放入栈；读到 ]，查表得到期望左括号是 [，与栈顶一致；再读到 }，查表得到 {，也与栈顶一致；最后栈为空。

6.3 代码实现

C 标准库没有直接内置 HashMap 和 Deque；在只有三种规则时，用 switch 查询对应关系、用字符数组保存待匹配括号即可。C++、Java、Python、JavaScript 则采用各自适合的映射容器。数据结构 API 可以不同，匹配规则与执行过程保持一致。

::: code-group C|C++|Java|Python|JavaScript

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

/* C 标准库没有内置哈希映射；本题只有三种配对，用 switch 即可。 */
static char expectedLeft(char right) {
    switch (right) {
        case ')': return '(';
        case ']': return '[';
        case '}': return '{';
        default: return '\0';
    }
}

bool isValid(char *s) {
    size_t n = strlen(s);
    // 括号必须成对出现；奇数长度不可能完全匹配。
    if (n % 2 != 0) return false;
    // 建立空栈，存储仍需要匹配的字符。
    char *stack = malloc(n + 1);
    if (stack == NULL) return false;
    size_t top = 0;

    // 从左到右扫描，每次只处理一个括号。
    for (size_t i = 0; i < n; ++i) {
        char c = s[i];
        // C 用 switch 查询这一个字符应匹配的左括号。
        char left = expectedLeft(c);
        // 非右括号即左括号，直接入栈。
        if (left == '\0') {
            stack[top++] = c;
        } else {
            // 先防空栈，再取出最近左括号检查是否符合映射关系。
            if (top == 0 || stack[--top] != left) {
                free(stack);
                return false;
            }
        }
    }

    // 处理完所有字符后，只有没有遗留待匹配字符才有效。
    bool ok = (top == 0);
    free(stack);
    return ok;
}

#include <deque>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        // 括号必须成对出现；奇数长度不可能完全匹配。
        if (s.size() % 2 != 0) return false;
        // 建立配对关系；查到右括号时可获得它要求的左括号。
        const unordered_map<char, char> matching = {
            {')', '('}, {']', '['}, {'}', '{'}
        };
        // 建立空栈，存储仍需要匹配的字符。
        deque<char> stack;
        // 从左到右扫描，每次只处理一个括号。
        for (char c : s) {
            // 判断当前字符是不是右括号；右括号需要检查规则表。
            auto it = matching.find(c);
            // 不是右括号，则按题目限定可认定为左括号，压入栈。
            if (it == matching.end()) {
                stack.push_back(c);
            } else {
                // 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
                if (stack.empty() || stack.back() != it->second)
                    return false;
                stack.pop_back();
            }
        }
        // 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return stack.empty();
    }
};

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

class Solution {
    public boolean isValid(String s) {
        // 括号必须成对出现；奇数长度不可能完全匹配。
        if (s.length() % 2 != 0) return false;
        // 建立配对关系；查到右括号时可获得它要求的左括号。
        Map<Character, Character> matching = Map.of(
            ')', '(', ']', '[', '}', '{'
        );
        // 建立空栈，存储仍需要匹配的字符。
        Deque<Character> stack = new ArrayDeque<>();
        // 从左到右扫描，每次只处理一个括号。
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 判断当前字符是不是右括号；右括号需要检查规则表。
            if (matching.containsKey(c)) {
                // 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
                if (stack.isEmpty() || stack.pop() != matching.get(c))
                    return false;
            } else {
                stack.push(c);
            }
        }
        // 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return stack.isEmpty();
    }
}

from collections import deque

class Solution:
    def isValid(self, s: str) -> bool:
        # 括号必须成对出现；奇数长度不可能完全匹配。
        if len(s) % 2 != 0:
            return False
        # 建立配对关系；查到右括号时可获得它要求的左括号。
        matching = {')': '(', ']': '[', '}': '{'}
        # 建立空栈，存储仍需要匹配的字符。
        stack = deque()
        # 从左到右扫描，每次只处理一个括号。
        for c in s:
            # 判断当前字符是不是右括号；右括号需要检查规则表。
            if c in matching:
                # 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
                if not stack or stack.pop() != matching[c]:
                    return False
            else:
                stack.append(c)
        # 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return not stack

var isValid = function(s) {
    // 括号必须成对出现；奇数长度不可能完全匹配。
    if (s.length % 2 !== 0) return false;
    // 建立配对关系；查到右括号时可获得它要求的左括号。
    const matching = new Map([
        [')', '('], [']', '['], ['}', '{']
    ]);
    // JS 数组的 push/pop 即可实现末端栈操作。
    // 建立空栈，存储仍需要匹配的字符。
    const stack = [];
    // 从左到右扫描，每次只处理一个括号。
    for (const c of s) {
        // 判断当前字符是不是右括号；右括号需要检查规则表。
        if (matching.has(c)) {
            // 先排除空栈，否则右括号没有匹配对象（也避免非法出栈）。
            if (stack.length === 0 || stack.pop() !== matching.get(c))
                return false;
        } else {
            stack.push(c);
        }
    }
    // 处理完所有字符后，只有没有遗留待匹配字符才有效。
    return stack.length === 0;
};

:::

6.4 复杂度分析

• 时间复杂度：本题为 O(n)。 仅有三组固定规则，查表为常数级工作，遍历一次字符串即可完成判断。对于常规哈希表的通用分析，哈希查找通常按期望 O(1) 讨论。
• 辅助空间复杂度：最坏 O(n)。 栈可能暂存 O(n) 个左括号，映射表只保存三条规则，占 O(1)。

这一步不是“必然更快”。 构造映射表有额外成本，小规模固定规则时可能比简单的三个条件判断更慢。它的主要价值是规则集中、职责清楚、便于扩展。如果将来支持额外定界符，要同时检查这些定界符的词法含义以及嵌套规则，而不只是机械新增一个 Map 条目。

七、解法五：数组模拟栈——进一步控制内存与常数开销

7.1 核心思想

栈不是必须由某个 Stack 类实现。栈真正需要的操作其实只有两个：从末尾放入一个元素、从末尾取走最近放入的元素。普通数组也能完成这两件事。

先申请一个长度为 n 的字符数组 stack，再设置整数 top = 0。本文统一规定：

• stack[0] 到 stack[top - 1] 是当前有效的栈元素。
• top 表示栈里有多少元素，也等于下一次入栈要写入的位置。
• top == 0 表示栈为空；top > 0 才可以出栈。

借用上一种“提前保存右括号”的思路，可以做到仅靠数组下标与字符比较就完成判断。

7.2 执行步骤

1. 读取字符串长度 n。如果 n 是奇数，直接返回 false。
2. 建立容量为 n 的字符数组 stack，初始化 top = 0。最坏情况下每个字符都是左括号，因此 n 个槽位一定足够。
3. 从左向右处理当前字符 c。如果 c 是 (、[ 或 {，先找出它对应的右括号 expected。
4. 把 expected 写入 stack[top]，随后执行 top = top + 1。先写再加，因为 top 原本指向下一处空位置。
5. 如果读到右括号，先判断 top == 0 是否成立。若成立，说明没有任何等待匹配的括号，直接返回 false，绝不能读取 stack[-1]。
6. 如果栈非空，先让 top = top - 1，然后读取 stack[top]，与当前右括号比较。若不同，返回 false；若相同，继续处理后面的字符。
7. 全部处理完后检查 top：等于 0，说明所有括号均已闭合，返回 true；否则返回 false。

特别容易混淆的细节： 如果已经保存两个字符，分别在数组下标 0 和 1，那么此时 top = 2。最近压入的字符在 stack[1]，而不是 stack[2]。因此出栈必须先减 1，才能读取正确的位置。

当前输入	动作	当前有效栈（底 → 顶）	top
开始	创建数组	空	0
(	写入)后top++	)	1
[	写入]后top++	) ]	2
]	先--top，再读到]	)	1
)	先--top，再读到)	空	0
结束	判断top == 0	空	返回true

数组里的旧字符即使没有被擦除，只要已经不在有效区间 [0, top) 中，就不再属于栈，也不影响最终结果。

7.3 代码实现

Java 的 char[] 可以直接存原始字符，避免 Deque<Character> 的泛型容器与可能的装箱开销；其他语言也可以用数组或类似的线性存储结构。C 语言没有标准库内建的栈，所以它前面几种写法实际上也已经借助数组实现栈；本节的优化重点尤其体现在 Java 等具有通用对象容器的语言中。

::: code-group C|C++|Java|Python|JavaScript

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool isValid(char *s) {
    size_t n = strlen(s);
    // 括号必须成对出现；奇数长度不可能完全匹配。
    if (n % 2 != 0) return false;
    // 一次准备 n 个槽位；top 表示有效元素个数（下一写入下标）。
    char *stack = malloc(n + 1);
    if (stack == NULL) return false;
    size_t top = 0;

    // 从左到右扫描，每次只处理一个括号。
    for (size_t i = 0; i < n; ++i) {
        char c = s[i];
        // 将期待字符写到 stack[top]，随后 top 加一。
        if (c == '(') stack[top++] = ')';
        else if (c == '[') stack[top++] = ']';
        else if (c == '{') stack[top++] = '}';
        // 空栈直接失败；否则取出栈顶期待字符，和当前字符比较。
        else if (top == 0 || stack[--top] != c) {
            free(stack);
            return false;
        }
    }

    // 处理完所有字符后，只有没有遗留待匹配字符才有效。
    bool ok = (top == 0);
    free(stack);
    return ok;
}

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        // 括号必须成对出现；奇数长度不可能完全匹配。
        if (s.size() % 2 != 0) return false;
        // 一次准备 n 个槽位；top 表示有效元素个数（下一写入下标）。
        vector<char> stack(s.size());
        size_t top = 0;

        // 从左到右扫描，每次只处理一个括号。
        for (char c : s) {
            // 将期待字符写到 stack[top]，随后 top 加一。
            if (c == '(') stack[top++] = ')';
            else if (c == '[') stack[top++] = ']';
            else if (c == '{') stack[top++] = '}';
            // 空栈直接失败；否则取出栈顶期待字符，和当前字符比较。
            else if (top == 0 || stack[--top] != c) return false;
        }
        // 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return top == 0;
    }
};

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        // 括号必须成对出现；奇数长度不可能完全匹配。
        if (n % 2 != 0) return false;
        // 一次准备 n 个槽位；top 表示有效元素个数（下一写入下标）。
        char[] stack = new char[n];
        int top = 0;

        // 从左到右扫描，每次只处理一个括号。
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 将期待字符写到 stack[top]，随后 top 加一。
            if (c == '(') stack[top++] = ')';
            else if (c == '[') stack[top++] = ']';
            else if (c == '{') stack[top++] = '}';
            // 空栈直接失败；否则取出栈顶期待字符，和当前字符比较。
            else if (top == 0 || stack[--top] != c) return false;
        }
        // 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return top == 0;
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        # 括号必须成对出现；奇数长度不可能完全匹配。
        if len(s) % 2 != 0:
            return False
        # 一次准备 n 个槽位；top 表示有效元素个数（下一写入下标）。
        stack = [None] * len(s)
        matching = {'(': ')', '[': ']', '{': '}'}
        top = 0

        # 从左到右扫描，每次只处理一个括号。
        for c in s:
            # 将期待字符写到 stack[top]，随后 top 加一。
            if c in matching:
                stack[top] = matching[c]
                # 入栈：已写入一个新元素，有效栈长度加一。
                top += 1
            else:
                # 先判断是否为空，再取出栈顶进行严格比较。
                if top == 0:
                    return False
                # 出栈：先缩小有效区间，再读取最后一个元素。
                top -= 1
                if stack[top] != c:
                    return False
        # 处理完所有字符后，只有没有遗留待匹配字符才有效。
        return top == 0

var isValid = function(s) {
    // 括号必须成对出现；奇数长度不可能完全匹配。
    if (s.length % 2 !== 0) return false;
    // 一次准备 n 个槽位；top 表示有效元素个数（下一写入下标）。
    const stack = new Array(s.length);
    let top = 0;

    // 从左到右扫描，每次只处理一个括号。
    for (const c of s) {
        // 将期待字符写到 stack[top]，随后 top 加一。
        if (c === '(') stack[top++] = ')';
        else if (c === '[') stack[top++] = ']';
        else if (c === '{') stack[top++] = '}';
        else if (top === 0 || stack[--top] !== c) return false;
    }
    // 处理完所有字符后，只有没有遗留待匹配字符才有效。
    return top === 0;
};

:::

7.4 复杂度分析

• 时间复杂度：O(n)。 每个字符只处理一次，写入或读取指定数组下标是常数级操作。
• 辅助空间复杂度：O(n)。 实现一开始就申请了长度为 n 的字符数组；即使实际嵌套深度很浅，已经预分配的数组也不会因此缩小。

数组模拟栈并没有把 O(n) 优化为 O(1)。 它改善的是某些语言环境下的常数开销：省去部分集合操作、减少元素装箱与额外对象管理；但是否明显更快，需要在具体运行环境做基准测试，不能根据 LeetCode 的单次击败率下结论。

八、总结：不同情况下该选哪种方法？

五种方法的改进方向并不完全相同：暴力法 → 栈法是算法复杂度的提升；标准栈 → 提前存右括号是状态表示的简化；映射表 + 双端队列注重结构和扩展性；数组模拟栈主要减少特定语言实现中的常数开销。

解法	时间复杂度	辅助空间复杂度	主要特点	适用情况
① 暴力枚举消除	最坏O(n²)	O(n)上界	反复删除合法相邻括号对	初次理解问题、短串演示、对照验证
② 标准栈	O(n)	最坏O(n)	保存未匹配的左括号，直观体现后进先出	学习栈、面试解释正确性
③ 提前存右括号	O(n)	最坏O(n)	保存期待字符，出栈只做相等比较	LeetCode 常规提交、手写简洁实现
④ 映射表 + 双端队列	O(n)	最坏O(n)	顺序与配对规则分离，便于维护	Java 工程逻辑、可配置匹配规则
⑤ 数组模拟栈	O(n)	O(n)（预分配）	自己管理数组与栈顶下标，控制常数开销	算法竞赛、性能分析、理解栈底层实现

怎样判断该用哪一种？

遇到相似题目时，可以先问自己三个问题：

1. 能不能直接化简？ 例如不断删掉相邻的 ()，这能迅速帮助你验证想法，但可能存在反复扫描的问题。
2. 要不要记住“最近一个尚未完成的结构”？ 如果下一次匹配必须优先处理最近的未完成对象，就应首先考虑栈。
3. 真正想优化的是什么？ 如果是减少重复扫描，换算法；如果是让判断更清晰，改变栈中保存的状态；如果是便于扩展，抽出映射规则；如果是降低集合开销，再考虑数组模拟栈。

最终记住一句话：括号匹配之所以想到栈，不是因为题目里有括号，而是因为“最后出现、尚未完成的左括号必须最先闭合”。

这套判断方式也适用于编辑器的括号高亮、简单表达式检查、嵌套结构解析等场景；如果输入涉及字符串字面量、转义字符或注释，还需要额外的词法规则，不能直接把本题代码原封不动搬过去。