景真

外观

有效的括号

约 551 字大约 2 分钟

2025-02-24

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

如果只有圆括号，通过左括号的次数（正代表左括号，负代表右括号）就能正确判断有效性。对于三种括号的情况，这种思路是不行的， 比如说只有一个括号的情况下 (()) 是有效的，但是多种括号的情况下， [(]) 显然是无效的。

仅仅记录每种左括号出现的次数已经不能做出正确判断了，我们要加大存储的信息量，可以利用栈来模仿类似的思路。

栈

  • 遇到左括号就入栈，
  • 遇到右括号就检查是否匹配栈顶元素，
    • 如果匹配，则弹出栈顶元素，
    • 否则返回false。
  • 最后检查栈是否为空。

栈的特点是就近处理，类似时序信息，离现在近的信息更重要。

class Solution {
    public boolean isValid(String str) {
        Deque<Character> left = new LinkedList<>();
        
        for (char c : str.toCharArray()) {
            // 如果是左括号，则直接入栈
            if (c == '(' || c == '{' || c == '[') {
                left.push(c);
            } else {
                // 如果是右括号，检查是否匹配栈顶元素，注意判空。
                if (!left.isEmpty() && leftOf(c) == left.peek()) {
                    // 注意 Deque 的 push、pop、peek 都是操作栈顶元素，即最左端的元素！
                    left.pop();
                } else {
                    // 和最近的左括号不匹配
                    return false;
                }
            }
        }
        
        // 是否所有的左括号都被匹配了，即虽然所有的右括号都被匹配了，但是可能左括号比较多。重点。
        return left.isEmpty();
    }

    char leftOf(char c) {
        if (c == '}') return '{';
        if (c == ')') return '(';
        return '[';
    }
}
  • 时间复杂度: O(n)O(n)，因为只遍历了一遍字符串。
  • 空间复杂度: O(n)O(n)，最坏情况下，全部都是左括号，所以栈的大小为 O(n)O(n)。