【LeetCode刷题日记】20.有效的括号

作者：北极的代码 简介：Java后端学习者 | 专栏：苍穹外卖日记、SSM框架深入、JavaWeb 格言：命运的结局尽可永在，不屈的挑战却不可须臾或缺！

栈的应用：一文讲透“有效的括号”问题

前言

前天一次性做了好几道题目，但没有时间发出来，今天一次性全发出来。其实整理思路也是挺累的，需要再想一遍，不过确实能提高熟练度。

摘要

这篇文章讲解如何用栈结构判断括号字符串的有效性。

题目要求判断包含三种括号（()、[]、{}）的字符串是否有效，即左括号必须按正确顺序闭合。

通过示例详细分析了匹配过程：

• 遇到左括号时，将对应右括号压入栈
• 遇到右括号时，检查栈顶元素是否匹配

文章指出了三种失败情况以及成功条件，并给出了Java实现代码（使用Deque模拟栈操作）。这种方法通过预存对应右括号简化了匹配判断，时间复杂度为 O(n)。

题目背景：LeetCode 20. 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确的顺序闭合
3. 空字符串可被认为是有效字符串

示例：

题目解析

这道题目其实是《数据结构与算法》中的经典例题，也是栈最常见的应用。

题意就像我们在写代码的过程中，要求括号的顺序是一致的——有左括号，相应的位置必须要有对应的右括号。

如果你还记得编译原理的话，编译器在词法分析过程中处理括号、花括号等符号的逻辑，也是使用了栈这种数据结构。

一个容易误解的地方

不仅仅是判断一个左括号对应一个右括号，还要判断交叉嵌套问题。

比如 "([)]" 这种写法，看起来每种括号都出现了，但顺序是错的，应该返回 false。

三种失败情况

成功条件：字符串遍历完之后，栈为空 → 全部匹配 ✅

代码实现

这里使用了一个比较巧妙的方法：

• 遇到左括号时，往栈里存放对应的右括号
• 遇到右括号时，直接比较是否与栈顶元素相等即可

示例演示："{[]}"

遍历结束，栈为空 → true

示例演示："([)]"（错误情况）

完整代码（Java）

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();
    }
}
```java

这道题虽然简单，但很好地体现了栈“后进先出”的特性在括号匹配问题中的天然适用性。通过“压入对应右括号”的技巧，代码可以写得非常简洁优雅。

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、关注～