本文详解括号匹配问题的正确解法：指出常见错误思路（如错位索引、忽略嵌套）的根本缺陷，并完整实现基于栈的高效验证算法，支持 (), {}, [] 三类括号的嵌套与顺序校验。
本文详解括号匹配问题的正确解法：指出常见错误思路（如错位索引、忽略嵌套）的根本缺陷，并完整实现基于栈的高效验证算法，支持 `()`, `{}`, `[]` 三类括号的嵌套与顺序校验。
你提供的代码试图通过“配对位置检查”来验证括号有效性，但存在两个关键逻辑错误，导致连最简单的 "()" 都返回 false：
索引越界与错位访问：s.charAt(2 * index + 1) 和 s.charAt(2 * index + 2) 在 index = 0 时分别访问下标 1 和 2，而字符串 "()" 长度仅为 2，下标最大为 1 —— 这直接引发 StringIndexOutOfBoundsException（或在某些运行环境下静默出错）。更根本的是，charAt() 的索引从 0 开始，而非 1，因此你的配对逻辑完全错位。
无法处理嵌套结构：该方法仅检查相邻偶数位与奇数位的“硬配对”，假设所有括号都是并列平铺的（如 "()[]"），但真实场景中大量存在嵌套（如 "[()]"、"{[()]}"）。这类结构要求“后开先闭”，必须依赖后进先出（LIFO）语义——而这正是栈（Stack） 的天然优势。
✅ 正确解法：使用栈模拟括号的入栈与匹配出栈过程
- 遍历字符串每个字符：
- 若为左括号 (、{、[ → 入栈；
- 若为右括号 )、}、] → 检查栈顶是否为对应左括号；若不匹配或栈为空，则无效；
- 遍历结束后，栈必须为空才算完全匹配。
以下是 Java 标准实现（含清晰注释）：
import java.util.*;
class Solution {
public boolean isValid(String s) {
// 使用 Deque 作为栈（比 Stack 更推荐，线程安全且性能优）
Deque<Character> stack = new ArrayDeque<>();
// 定义右括号到左括号的映射，便于快速匹配
Map<Character, Character> pairs = Map.of(
')', '(',
'}', '{',
']', '['
);
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) {
// 左括号：直接入栈
stack.push(c);
} else if (pairs.containsKey(c)) {
// 右括号：检查栈顶是否匹配
if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
return false;
}
}
// 字符非法（题目保证只含括号，此处可省略校验）
}
// 所有括号匹配完毕，栈应为空
return stack.isEmpty();
}
}? 关键注意事项：
- 不要用 Stack 类：Java 官方文档明确建议使用 Deque（如 ArrayDeque）替代已过时的 Stack；
- 空栈校验不可省略：遇到右括号时若栈为空（如 ")"），说明缺少对应左括号，立即返回 false；
- 时间复杂度 O(n)，空间复杂度 O(n)（最坏情况全为左括号）；
- 该解法天然支持任意深度嵌套、混合类型（如 "{[()]}"）、以及空字符串 ""（返回 true）。
总结：括号匹配本质是顺序依赖型配对问题，必须借助栈维护“待匹配的左括号序列”。任何绕过栈、试图靠位置计算或哈希映射直接配对的思路，在面对嵌套时必然失效。掌握这一模式，是解决括号类问题（如括号生成、最长有效括号等）的基石。
