LeetCode 20. 有效的括号
题目描述
题意分析
字符串只包含三种括号的左右两侧。要判断整串是否有效，每个右括号都必须有同类型的左括号与之配对，且内部括号先闭合、外部括号后闭合，不能交叉匹配，也不能留下未配对的括号。
只统计左右括号的数量无法判断嵌套顺序。扫描到一个右括号时，真正需要检查的是最近出现、但尚未闭合的那个左括号；更早的左括号必须等内部这一层闭合后才能处理。
解法：栈模拟最近匹配
核心思路
[!blue]
后出现的左括号必须先被关闭，这正好符合栈的后进先出顺序。代码不直接保存左括号，而是保存它所期待的右括号；栈顶始终代表下一次允许闭合的括号类型。
遇到左括号时，把对应的右括号压入栈，表示进入了一层新的嵌套。遇到右括号时，如果栈为空，就没有左括号能与它配对；如果它与栈顶不同，就试图越过尚未关闭的内层括号，或使用了错误的类型。这两种情况都已经使当前前缀无效，后续字符无法修复，可以立即返回
false。只有与栈顶相同时，才能弹出这一项，表示最内层的一对括号已经闭合。更外层的期望重新成为栈顶，继续等待后续字符。因此处理完每个字符后，栈恰好保存已经出现、仍未闭合的各层括号所期待的右侧字符。
扫描过程中没有冲突还不够：结束时如果栈不为空，就仍有左括号没有对应的右括号。只有整串处理完且栈为空，所有括号才都按正确类型与顺序完成配对。
解题步骤
- 创建空栈，从左到右扫描字符串。
- 遇到左括号，压入它对应的右括号。
- 遇到右括号，先检查栈是否为空，再检查它是否与栈顶相同；任一条件不满足就返回
false。- 匹配成功则弹出栈顶，继续扫描。Java 在比较时直接弹出，Go 在比较成功后弹出，含义相同。
- 扫描结束后，返回栈是否为空。
代码实现
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : s.toCharArray()) {
if (ch == '(') {
// 栈里存期望出现的右括号，后进的左括号应先闭合。
stack.push(')');
} else if (ch == '[') {
stack.push(']');
} else if (ch == '{') {
stack.push('}');
} else if (stack.isEmpty() || stack.pop() != ch) {
// 栈为空或期望不匹配，当前右括号无法正确闭合。
return false;
}
}
return stack.isEmpty();
}
}
func isValid(s string) bool {
stack := []byte{}
for i := 0; i < len(s); i++ {
ch := s[i]
if ch == '(' {
// 栈里存期望出现的右括号，后进的左括号应先闭合。
stack = append(stack, ')')
} else if ch == '[' {
stack = append(stack, ']')
} else if ch == '{' {
stack = append(stack, '}')
} else if len(stack) == 0 || stack[len(stack)-1] != ch {
// 栈为空或期望不匹配，当前右括号无法正确闭合。
return false
} else {
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}
复杂度分析
- 时间复杂度：$O(n)$，每个字符只处理一次。
- 空间复杂度：$O(n)$，最坏情况下所有字符都是左括号。
关键点总结
[!green]
- 栈顶始终是当前右括号唯一可以匹配的位置。
- 直接保存期望的右括号，匹配时只需比较一次。
- 中途检查多余或错配的右括号，最后检查残留的左括号。
易错点总结
[!yellow]
- 只比较左右括号的数量，无法检查括号类型和嵌套顺序。
- 读取栈顶前必须先判空，否则会抛异常或越界。
- 匹配成功后要弹栈，扫描结束后还要确认栈为空。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 32. 最长有效括号 | 困难 | 合法性同样与括号匹配有关，原题寻找最长合法连续区间，本题判断整串是否全部匹配。 |
| 1249. 移除无效的括号 | 中等 | 同样利用括号匹配识别无效部分；1249只处理圆括号并删除最少括号、保留普通字母，本题处理三种括号且不允许修改，必须检查类型与嵌套顺序。 |
| 补充题 176. 括号配对与未匹配数量统计 | 中等 | 括号匹配系列。单一括号类型可把未匹配左括号栈简化为计数器；补充题统计配对与剩余数量，本题还检查类型及完整合法性。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！