LC20. 有效的括号

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 1、左括号必须用相同类型的右括号闭合。 2、左括号必须以正确的顺序闭合。

题目解析

题目在说什么

这道题是让我们判断一个只包含括号的字符串是不是“有效的”。 什么是“有效”呢？想象一下你写数学算式：(1+2) 是对的，但 (1+2 就少了一个右括号，不对。 这里的规则更严格：

• 左括号必须用同类型的右括号关闭，比如 ( 必须配 )，不能配 ]。
• 括号必须按正确的顺序关闭，比如 ([)] 就不行，因为 [ 还没关就关了 (，顺序乱了。

所以，我们要检查字符串里的括号是不是成双成对、顺序正确。

思路是怎么来的

你可能会想：怎么检查呢？一个简单的方法是用“栈”这个数据结构。 栈就像一摞盘子：你只能从最上面拿盘子，放盘子也只能放最上面。

为什么用栈？ 因为括号匹配有个特点：后遇到的左括号，要先匹配。 比如 ([)]：先遇到 (，再遇到 [，但正确顺序应该是先关 [ 再关 (，所以 [ 是后遇到的左括号，它必须最先被匹配。 这正好符合栈“后进先出”的特性——后放进去的，先拿出来。

生活化比喻： 想象你在玩一个“括号消除”游戏。

• 遇到左括号，就把它放进一个盒子里（栈）。
• 遇到右括号，就看看盒子最上面的左括号是不是和它配对。
• 如果配对，就把那个左括号拿出来（消除）。
• 如果不配对，或者盒子是空的，说明这串括号无效。

最后，如果盒子空了，说明所有括号都配对了，有效；否则无效。

代码逐步拆解

我们来看参考代码，一步步拆解。

1. 快速判断：字符串长度是奇数就直接无效

if (s.length() % 2 == 1) {
    return false;
}

为什么？ 括号都是成对出现的，所以有效字符串的长度一定是偶数。如果是奇数，肯定有括号落单，直接返回 false。 这就像你穿袜子：如果袜子总数是奇数，肯定有一只没配对。

2. 创建栈

Stack<Character> stack = new Stack<Character>();

栈用来存放我们遇到的左括号。 Character 是 Java 中表示单个字符的类型，比如 '('、')'。

3. 把字符串转成字符数组，方便逐个处理

char charArray[] = s.toCharArray();

这样我们就可以用循环一个一个看每个字符了。

4. 遍历每个字符

for (int i = 0; i < charArray.length; i++) {
    char c = charArray[i];

c 就是当前看到的字符。

5. 遇到左括号，就压入栈

if (c == '(') {
    stack.push('(');
} else if (c == '[') {
    stack.push('[');
} else if (c == '{') {
    stack.push('{');
}

为什么压入左括号？ 因为左括号是“等待被匹配”的，我们把它存起来，等遇到右括号时再检查。

6. 遇到右括号，进行处理

else {
    if (stack.isEmpty()) return false;
    char top = stack.peek();
    if (top == '(' && c == ')' || top == '[' && c == ']' || top == '{' && c == '}') {
        stack.pop();
    } else {
        return false;
    }
}

这里分三步：

• 检查栈是否为空：如果栈是空的，说明没有左括号可以匹配这个右括号，比如字符串以 ) 开头，直接无效。
• 查看栈顶元素：stack.peek() 会返回栈最上面的左括号，但不会移除它。