LeetCode 20. 有效的括号
目录
题目描述
题意分析
输入是一个只由
(、)、[、]、{、}六种字符组成的字符串，要求回答它是否「有效」，返回布尔值。题面把「有效」拆成了三个条件：每个左括号都必须由同类型的右括号闭合；闭合必须按正确的顺序发生；不同种类的括号之间不能交叉。三条各有各的反例：
(]违反第一条，类型对不上；)(违反第二条，右括号出现在它要闭合的左括号之前；([)]里六种字符的数量完全配平，却因为(和[互相穿插而违反第三条。把三条合起来推，能得到一个比条件本身更好用的结论：当扫描到某个右括号时，它能闭合、且只能闭合当前所有尚未闭合的左括号中最晚出现的那一个。如果它去闭合更早的那个左括号，夹在中间的那些左括号就会被跨越，立刻构成交叉。也就是说，配对关系是「最近未闭合者优先」，一个后来的左括号一定比先来的左括号更早被闭合——这种后进先出的次序，是本题唯一真正的算法信号，剩下的都只是实现细节。
还有一个免费的必要条件：有效串必然由若干成对的括号拼成，长度一定是偶数，所以长度为奇数的输入可以直接判定无效。反过来不成立，偶数长度并不保证有效，
)(就是反例。几个边界情形值得先想清楚：空串里没有任何左括号需要闭合，也没有任何右括号无处安放，视为有效；只有右括号（如
)）一定无效，它找不到可闭合的对象；只有左括号（如(）也一定无效，它永远等不到闭合。这三种情况分别对应「什么都不做」「中途就失败」「扫完才失败」，实现时必须都覆盖到。
解法：栈模拟最近匹配
核心思路
栈保存每个左括号期望遇到的右括号。遇到左括号就压入对应右括号；遇到右括号时，它必须等于栈顶。
扫描中出现空栈或类型不匹配，立即返回
false；扫描结束后栈为空才有效。
解题步骤
- 从左到右扫描字符串。
- 遇到左括号，压入它对应的右括号。
- 遇到右括号，若栈为空或栈顶与当前字符不同，返回
false。- 扫描结束，返回栈是否为空。
代码实现
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)$，最坏情况下所有字符都是左括号。
关键点总结
- 栈顶始终是当前右括号唯一可以匹配的位置。
- 直接保存期望的右括号，匹配时只需比较一次。
- 中途检查多余或错配的右括号，最后检查残留的左括号。
易错点总结
- 只比较括号数量会漏掉
([)]这类顺序错误。- 读取栈顶前必须先判空，否则会抛异常或越界。
- 匹配成功后要弹栈，扫描结束后还要确认栈为空。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 22. 括号生成 | 中等 | 从「判断给定串是否有效」反过来变成「构造出全部有效串」，靠回溯枚举而不是一次扫描 |
| 32. 最长有效括号 | 困难 | 不再只回答有效与否，而要求最长有效子串的长度，栈里存的是下标而非括号本身 |
| 71. 简化路径 | 中等 | 同一个「最近未处理项」模型的非括号版本：目录名入栈、.. 触发出栈 |
| 150. 逆波兰表达式求值 | 中等 | 栈里存的是运算数，弹出后要做算术运算，而不是做配对校验 |
| 301. 删除无效的括号 | 困难 | 从判定升级成「删最少字符使其有效」并输出所有方案，需要搜索加去重 |
| 678. 有效的括号字符串 | 中等 | 只有一种括号但多了通配符 *，栈顶不再唯一确定，要维护未闭合数量的可行区间 |
| 856. 括号的分数 | 中等 | 输入已保证有效，重点从校验转向沿嵌套结构累加分值 |
| 1003. 检查替换后的词是否有效 | 中等 | 匹配单位从「一对括号」变成固定的三字符子串 abc，栈上做的是子串消除 |
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 消除条件从「类型配对」换成「与栈顶字符相同」，且要返回消除后的字符串 |
| 1249. 移除无效的括号 | 中等 | 串中混有普通字母，需要记录待删下标并重建字符串，而不是只返回布尔值 |
| 1544. 整理字符串 | 简单 | 相邻消除的条件是同字母且大小写相反，栈的用法与本题一致但配对规则换了 |
| 1614. 括号的最大嵌套深度 | 简单 | 输入已保证有效且只有一种括号，只求最大嵌套深度，一个计数器就能替代栈 |