栈与队列简单1 种解法
#20有效的括号
判断括号字符串是否按正确类型和嵌套顺序闭合。
#字符串#栈
原题
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
示例 5：
输入：s = "([)]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
解题主线
- 读到左括号时压入其期望的右括号，读到右括号时只需与栈顶比较。
解法 1：期望右括号栈
左括号入栈时直接压入匹配的右括号；右括号必须弹出相同字符。
-
时间复杂度： O(n)
-
空间复杂度： O(n)
import java.util.ArrayDeque;
import java.util.Deque;
final class Solution {
public boolean isValid(String s) {
// 合法括号必须成对出现，奇数长度可直接排除。
if ((s.length() & 1) == 1) return false;
Deque<Character> expected = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 左括号直接压入期望的右括号，闭合时只需比较栈顶。
switch (c) {
case '(' -> expected.push(')');
case '[' -> expected.push(']');
case '{' -> expected.push('}');
default -> {
if (expected.isEmpty() || expected.pop() != c) return false;
}
}
}
return expected.isEmpty();
}
}实现提示
- 合并两个同题文件，保留等价实现中状态最少的一种。
边界与易错点
- 奇数长度必不合法，可先排除。
- 栈必须是方法内局部变量；旧实现使用实例字段会让重复调用共享残留状态。
- ArrayDeque 比遗留的 Stack 和以 LinkedList 实现的栈更合适。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
easy/Q020_isValid.javaeasy/Q020_isValidStr.java