#20
简单
高频
栈有效的括号
这是一道围绕字符串展开的高频练习。建议先掌握「栈」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
字符串
题目分析
给你一个只包含括号字符的字符串，括号类型包括小括号、中括号和大括号。
要求判断这个字符串是不是有效的括号序列。有效的意思是：
- 左右括号类型要匹配
- 关闭顺序也要正确
一句话概括：
判断括号字符串能不能按“最近打开、最先关闭”的顺序完全匹配成功。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：遇到左括号就入栈，遇到右括号就检查栈顶是否和它成对匹配。
推荐代码
推荐解法：栈
时间复杂度： O(n)
空间复杂度： O(n)
核心思路： 遇到左括号就入栈，遇到右括号就检查栈顶是否和它成对匹配。
import java.util.HashMap;
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
if (s == null) {
return true;
}
HashMap<Character, Character> keyWords = new HashMap<>();
keyWords.put(')', '(');
keyWords.put(']', '[');
keyWords.put('}', '{');
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (!stack.empty()) {
if (stack.peek() == keyWords.get(c)) {
stack.pop();
continue;
}
}
stack.push(c);
}
return stack.empty();
}结构化讲解
面试时怎么讲
开场思路
这题我会用栈，因为括号匹配要求最近打开的括号最先关闭。
核心过程
- 遍历字符串，左括号直接入栈。
- 遇到右括号时，先判断栈是否为空。
- 如果不为空，就检查它是否和栈顶左括号匹配，匹配则弹出。
- 遍历结束后，只有栈为空时字符串才有效。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(n)。
面试补一句：括号题真正的核心词不是“配对”，而是“顺序”。
核心思路
括号匹配的本质是“最近打开的括号必须最先关闭”，这正是栈的 LIFO 语义。左括号负责入栈建上下文，右括号负责消费当前上下文。
步骤讲解
1
左括号入栈
遍历字符串，遇到 (、[、{ 就先压入栈中。
为什么这样做：这些括号都在等待未来某个右括号来闭合。
对应代码提示：stack.push(ch);
2
遇到右括号先看栈是否为空
如果此时栈已经空了，说明没有对应的左括号可以匹配。
为什么这样做：关闭动作不能先于打开动作发生。
对应代码提示：if (stack.isEmpty()) return false;
3
只和栈顶括号做匹配
当前右括号只能去匹配最近一个尚未闭合的左括号，也就是栈顶。
为什么这样做：括号必须按正确顺序闭合，不能跨层匹配。
对应代码提示：if (top != pairs.get(ch)) return false;
4
遍历结束后确认栈为空
如果还有左括号留在栈里，说明它们没被闭合。
为什么这样做：有效字符串必须所有括号都成对消耗完。
对应代码提示：return stack.isEmpty();
易错点
只判断数量，不判断顺序
像 ([)] 数量是对的，但闭合顺序错误，仍然无效。
正确理解：必须和栈顶逐个匹配，而不是只统计个数。
右括号出现时没先判空
这会在空栈上取栈顶，直接出错。
正确理解：遇到右括号先检查
stack.isEmpty()。遍历结束后没检查残留左括号
字符串可能没有非法右括号，但仍然少了闭合。
正确理解：最终必须返回
stack.isEmpty()。复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(n)
比其他方案更好在哪里：比反复字符串替换的做法更直接，也更容易说明正确性。
适用判断：只要问题涉及成对符号、嵌套结构或最近未闭合元素，优先想到栈。
额外提醒
- 栈顶代表“当前最该被关闭的括号”。
其他语言 / 其他解法
string-replace
算法思路：
使用字符串替换法解决有效的括号问题，通过不断替换匹配的括号对，直到无法再替换为止。
核心思想：
- 遍历字符串，查找并替换所有匹配的括号对（()、[]、{}）
- 重复上述过程，直到字符串中不再包含任何匹配的括号对
- 最后检查字符串是否为空，若为空则括号有效，否则无效
复杂度分析：
- 时间复杂度：O(n^2)，每次替换操作需要遍历整个字符串，最坏情况下需要执行n/2次替换
- 空间复杂度：O(n)，替换过程中需要创建新的字符串
string-replace
算法思路：
使用字符串替换法解决有效的括号问题，通过不断替换匹配的括号对，直到无法再替换为止。
核心思想：
复杂度分析：
时间复杂度：O(n^2)
空间复杂度：O(n)
一句话思路：算法思路：
使用字符串替换法解决有效的括号问题，通过不断替换匹配的括号对，直到无法再替换为止。
核心思想：
- 遍历字符串，查找并替换所有匹配的括号对（()、[]、{}）
- 重复上述过程，直到字符串中不再包含任何匹配的括号对
- 最后检查字符串是否为空，若为空则括号有效，否则无效
- 时间复杂度：O(n^2)，每次替换操作需要遍历整个字符串，最坏情况下需要执行n/2次替换
- 空间复杂度：O(n)，替换过程中需要创建新的字符串
class Solution {
public boolean isValid(String s) {
if (s == null) {
return true;
}
// 字符串替换法：不断替换匹配的括号对，直到无法再替换为止
while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}
return s.length() == 0;
}动画演示
如果你还没完全看懂，可以展开动画演示。
栈动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
栈动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
有效的括号 - 动画演示
准备就绪 - 输入括号字符串，然后点击开始
(
)
[
]
{
}
}
栈状态：
空栈
string-replace动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
string-replace动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
有效的括号 - 字符串替换法动画演示
准备就绪 - 输入括号字符串，然后点击开始
步骤：0
当前字符串：
(
)
[
]
{
}
}
替换后：
(
)
[
]
{
}
}
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。