有效的括号

发表于 更新于 分类于

算法-有效的括号

背景

  • 算法–有效的括号

  • 博主以代码随想录算法公开课进行学习

题目

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

    有效字符串需满足：

    • 左括号必须用相同类型的右括号闭合。
    • 左括号必须以正确的顺序闭合。
    • 注意空字符串可被认为是有效字符串。

    示例 1:

    • 输入: “()”
    • 输出: true

    示例 2:

    • 输入: “()[]{}”
    • 输出: true

    示例 3:

    • 输入: “(]”
    • 输出: false

    示例 4:

    • 输入: “([)]”
    • 输出: false

    示例 5:

    • 输入: “{[]}”
    • 输出: true

思路

  • 核心逻辑：利用栈的「后进先出」特性匹配括号——左括号入栈，右括号匹配栈顶左括号，匹配成功则出栈，失败则直接返回false；
  • 具体步骤：
    • 遍历字符串每个字符：
      • 若为左括号（(/{/[）：将对应的右括号压入栈（简化后续匹配逻辑）；
      • 若为右括号：
        • 栈为空 → 无左括号匹配，返回false；
        • 栈顶元素≠当前右括号 → 类型不匹配，返回false；
        • 栈顶元素=当前右括号 → 匹配成功，弹出栈顶；
    • 遍历结束后：栈为空则所有括号匹配成功，否则存在未闭合的左括号。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for(int i = 0;i<s.length();i++){
             ch = s.charAt(i);
            if(ch == '('){
                deque.push(')');
            }else if(ch == '{'){
                deque.push('}');
            }else if(ch == '['){
                deque.push(']');
            }
            // 碰到右括号时：如果栈为空（无左括号匹配），或栈顶不是当前右括号（匹配失败）
            else if(deque.isEmpty()||deque.peek() != ch){
                return false;
            }
            // 右括号匹配成功 → 弹出栈顶
            else{
                deque.pop();
            }
        }
        return deque.isEmpty();
    }
}

总结

  • 有效的括号核心是栈+括号映射，利用栈的LIFO特性匹配嵌套括号；
  • 关键技巧：左括号入栈时压入对应右括号，简化后续匹配逻辑；
  • 面试需掌握「核心逻辑」「边界案例」「Deque替代Stack的原因」三个考点；
  • 复杂度为O(n)（时间+空间）