20. 有效的括号（Valid Parentheses）
频次 ★★★★★ · 难度 🟢 · 高频：全厂
题目
给定只包含 ()[]{} 的字符串，判断括号是否有效匹配（每个左括号必须以正确顺序被相同类型的右括号闭合）。
示例：
输入: s = "()[]{}"
输出: true
输入: s = "([)]"
输出: false
思路
括号匹配天然符合”最后打开的括号最先关闭”，是栈的经典应用：遇到左括号就压栈；遇到右括号就检查栈顶是否是对应的左括号——是则弹出继续，不是则直接判定无效。遍历结束后栈必须为空（不能有未闭合的左括号）。
代码
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(')
|| (c == ']' && top != '[')
|| (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}复杂度
- 时间：O(n) — 每个字符处理一次
- 空间：O(n) — 最坏情况下（全是左括号）栈存满所有字符
边界条件
- 空字符串：循环不执行，栈为空，返回
true（符合”空字符串合法”的通常约定）。 - 字符串长度为奇数：不可能完全匹配，但代码不需要专门判断奇偶——不匹配的情况会在遍历中被栈为空或类型不符捕获，或者遍历结束后栈非空被捕获。
- 只有右括号（如
")"）：第一次遇到右括号时栈为空，直接返回false。
变式
- 只有一种括号类型：可以退化成计数器（左括号 +1，右括号 -1，出现负数就是不合法），不需要真的用栈；一旦引入多种括号类型，必须用栈记录”最近打开的是哪种”。
- 允许字符串中包含其他普通字符（只校验括号是否匹配，忽略字母）：遍历时跳过非括号字符即可，栈逻辑不变。
易错点
- 遇到右括号时先判断
stack.isEmpty()再pop()，否则空栈弹出会抛异常（比如输入")"）。 - 遍历结束后要检查栈是否为空，漏掉这一步会把
"((("这种只有左括号的输入误判为合法。
面试追问
- 为什么这题必须用栈，用计数器行不行？ 单纯计数器只能处理一种括号类型（左右抵消）；一旦有
()[]{}多种类型混合，必须知道”最近打开的是哪一种”才能判断当前右括号是否匹配，这正是栈”后进先出”特性天然适合的场景。 - 如果要求返回第一个不匹配的位置（而不是只返回 true/false），怎么改？ 在两处返回
false的地方改成记录并返回当前下标i即可；如果是”栈非空”导致的不合法，需要额外记录栈底元素对应的原始下标才能定位第一个未闭合的左括号。
关联题
- 同套路：394. 字符串解码、150. 逆波兰表达式求值 —— 栈处理嵌套/后缀结构三件套
- 进阶：32. 最长有效括号 —— 栈存下标或 DP；856. 括号的分数
- 知识点：括号匹配是编译器语法检查的最小模型；栈与递归等价——本题的栈就是递归下降解析的显式化