标签#

• 平台：LeetCode
• 难度：简单
• 数据结构：字符串、栈
• 算法：模拟
• 解题模式：无

一、题目概述#

给定一个只包含圆括号、方括号和花括号的字符串，判断每个左括号是否由相同类型的右括号闭合，并且括号是否按正确顺序嵌套。当前实现对 null 和包含非括号字符的输入返回 false，空字符串返回 true。

二、解题思路#

括号匹配要求最后出现、尚未闭合的左括号最先被匹配，这正符合栈的后进先出特性。

遍历字符串时，遇到左括号就把它对应的右括号压入栈中；遇到右括号时，栈不能为空，并且栈顶保存的期望右括号必须等于当前字符。遍历结束后，只有栈为空才说明所有左括号都已正确闭合。

三、执行过程#

以 {[]} 为例：

1. 遇到 {，把期望的 } 压栈。
2. 遇到 [，把期望的 ] 压栈。
3. 遇到 ]，与栈顶匹配并弹出。
4. 遇到 }，与栈顶匹配并弹出。
5. 遍历结束时栈为空，返回 true。

对于 ([)]，读取 ) 时栈顶期望的是 ]，类型不匹配，立即返回 false。

四、代码实现#

1
import java.util.ArrayDeque;
2
import java.util.Deque;
3

4
public class LeetCode0020ValidParentheses {
5

6
    public boolean isValid(String text) {
7
        if (text == null) {
8
            return false;
9
        }
10

11
        Deque<Character> expectedClosingBrackets = new ArrayDeque<>();
12
        for (int i = 0; i < text.length(); i++) {
13
            char bracket = text.charAt(i);
14
            switch (bracket) {
15
                case '(' -> expectedClosingBrackets.push(')');
16
                case '[' -> expectedClosingBrackets.push(']');
17
                case '{' -> expectedClosingBrackets.push('}');
18
                case ')', ']', '}' -> {
19
                    if (expectedClosingBrackets.isEmpty()
20
                            || expectedClosingBrackets.pop() != bracket) {
21
                        return false;
22
                    }
23
                }
24
                default -> {
25
                    return false;
26
                }
27
            }
28
        }
29

30
        return expectedClosingBrackets.isEmpty();
31
    }
32
}

五、关键代码说明#

• Deque<Character>：使用双端队列接口表达栈行为。
• ArrayDeque：作为栈使用时比旧的 Stack 类更合适。
• 遇到左括号时压入对应右括号，使匹配逻辑只需直接比较字符。
• isEmpty() 必须在 pop() 前检查，防止右括号先出现时抛出异常。
• 遍历完成后再次检查栈是否为空，用于发现缺少右括号的情况。

六、复杂度分析#

• 时间复杂度：O(n)，其中 n 是字符串长度，每个字符最多入栈或出栈一次。
• 空间复杂度：O(n)，最坏情况下字符串全部由左括号组成，所有期望右括号都会保存在栈中。

七、注意事项#

• 只判断左右括号数量相等是不够的，还必须保证类型和嵌套顺序正确。
• 右括号出现时要先判断栈是否为空，避免空栈弹出异常。
• 遍历中全部匹配不代表最终有效，还要确认没有未闭合的左括号。
• 当前实现把空字符串视为有效括号串，因为其中不存在未匹配的括号。

八、面试知识点：栈与括号匹配#

括号匹配是栈的经典使用场景。嵌套结构中，最内层、最后出现的左括号必须最先闭合，因此需要后进先出的数据结构记录尚未匹配的括号。

当前实现没有把左括号本身压栈，而是直接压入它所期望的右括号。这样遇到右括号时只需要与栈顶做一次相等比较，不需要再编写三组左右括号映射判断。

面试中常见的错误包括：在检查空栈前调用 pop()、只比较括号数量、不检查最终栈是否为空，以及忽略 ([)] 这类数量相等但嵌套顺序错误的反例。

回到本题，面试时可以这样回答：遍历字符串，左括号对应的右括号入栈；遇到右括号时，如果栈为空或与栈顶不一致就返回 false。遍历结束后检查栈是否为空。每个字符只处理一次，所以时间复杂度是 O(n)，栈最坏保存 n 个字符，空间复杂度是 O(n)。