Hot 100 --- 有效的括号

本文概览：本文讲解有效的括号的核心思路：用栈实现括号的匹配，利用栈的后进先出特性，左括号入栈，右括号出栈匹配

一、题目

有效的括号

二、题目分析

1. 题目要求

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

有效字符串需要满足三个规则：

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

2. 例子分析

例子 1："(, (, }, )"

这个字符串违反了：

规则 1：} 没有对应的 {
规则 3：有两个 ( 但只有一个 )

例子 2："([)]"

这个字符串违反了：

规则 2：[ 比 ( 后出现，所以 [ 应该先闭合，但这里 ) 先闭合了 (

3. 核心观察

规则 2 其实就是栈的特性：先进后出。

后出现的左括号必须先闭合，这就是栈的后进先出（LIFO）特性。

思路：

遇到左括号，入栈
遇到右括号，出栈一个左括号，判断是否匹配
最后栈必须为空

三、思路概览

public boolean isValid(String s) {
    if(s.isEmpty()) {
        return true;
    }
    Map<Character, Character> map = new HashMap<>();
    map.put('{', '}');
    map.put('(', ')');
    map.put('[', ']');
    LinkedList<Character> stack = new LinkedList<>();
    for(char c : s.toCharArray()) {
        if(map.containsKey(c)) {
            stack.push(c);
        }else {
            if(stack.isEmpty() || map.get(stack.pop()) != c) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

思路简要说明：

用哈希表存储括号映射：{ → }，( → )，[ → ]
用栈存储左括号：遇到左括号入栈，遇到右括号出栈匹配
两个失败条件：
- 栈为空但遇到右括号 → 没有对应的左括号
- 出栈的左括号和当前右括号不匹配 → 类型不对
最后栈必须为空：否则说明有左括号没闭合

四、思路详解

第一步：为什么用栈？

题目要求"左括号必须以正确的顺序闭合"，这就是栈的特性：后进先出。

比如 "([)]"：

先出现 (，后出现 [
[ 应该先闭合，但 ) 先闭合了 (
违反了栈的顺序

如果用栈：

( 入栈
[ 入栈
遇到 )，出栈 [，发现 [ 和 ) 不匹配 → 返回 false

第二步：哈希表的作用

哈希表存储括号的映射关系：

1
2
3

map.put('{', '}');
map.put('(', ')');
map.put('[', ']');

这样判断左右括号是否匹配时，只需要查表：

1	map.get(stack.pop()) != c

如果出栈的左括号对应的右括号不等于当前右括号，说明不匹配。

第三步：两个失败条件

失败条件 1：stack.isEmpty()

遇到右括号时，栈为空，说明没有对应的左括号。

比如 ")"：

遇到 )，栈为空 → 返回 false

失败条件 2：map.get(stack.pop()) != c

出栈的左括号和当前右括号不匹配。

比如 "([)]"：

( 入栈
[ 入栈
遇到 )，出栈 [，map.get('[') = ]，不等于 ) → 返回 false

第四步：最后栈必须为空

遍历结束后，如果栈不为空，说明有左括号没闭合。

比如 "((("：

三个 ( 都入栈了
没有右括号匹配
最后栈不为空 → 返回 false

完整执行过程

以 "([{}])" 为例：

初始：stack = []

第 1 个字符 '('：
  是左括号，入栈
  stack = ['(']

第 2 个字符 '['：
  是左括号，入栈
  stack = ['(', '[']

第 3 个字符 '{'：
  是左括号，入栈
  stack = ['(', '[', '{']

第 4 个字符 '}'：
  是右括号，出栈 '{'
  map.get('{') = '}'，等于 '}' ✓
  stack = ['(', '[']

第 5 个字符 ']'：
  是右括号，出栈 '['
  map.get('[') = ']'，等于 ']' ✓
  stack = ['(']

第 6 个字符 ')'：
  是右括号，出栈 '('
  map.get('(') = ')'，等于 ')' ✓
  stack = []

遍历结束，栈为空 → 返回 true ✓

再以 "([)]" 为例：

初始：stack = []

第 1 个字符 '('：
  是左括号，入栈
  stack = ['(']

第 2 个字符 '['：
  是左括号，入栈
  stack = ['(', '[']

第 3 个字符 ')'：
  是右括号，出栈 '['
  map.get('[') = ']'，不等于 ')' ✗
  返回 false ✓

五、总结

有效的括号的核心思路：

用栈存储左括号：利用栈的后进先出特性
用哈希表存储映射：快速判断左右括号是否匹配
遇到左括号入栈：等待匹配
遇到右括号出栈匹配：判断是否匹配
两个失败条件：栈为空或类型不匹配
最后栈必须为空：否则有左括号没闭合

时间复杂度 O(n)，空间复杂度 O(n)。