LeetCode 20. 有效的括号

Categories:

Tags:

题目描述
思路分析
1. 解法一：栈模拟（推荐）
相似题目

题目描述

✅ 20. 有效的括号

题目：

给定一个仅包含字符 '('、')'、'{'、'}'、'['、']' 的字符串 s，判断字符串是否有效。有效条件：左括号必须用相同类型的右括号闭合；左括号必须按正确顺序闭合；每个右括号都有对应的相同类型左括号。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

1 <= s.length <= 10^4
s 仅由括号字符 '()[]{}' 组成

思路分析

解法一：栈模拟（推荐）

核心思路：

左括号入栈，右括号出现时检查栈顶是否为对应左括号。

若不匹配或栈为空，直接返回 false。

最终栈为空说明括号全部正确匹配。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，其中 n 表示栈的最大深度。

// 栈模拟括号匹配
class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if (c == ')' && top != '(') {
                    return false;
                }
                if (c == ']' && top != '[') {
                    return false;
                }
                if (c == '}' && top != '{') {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

// 栈模拟括号匹配
func isValid(s string) bool {
	stack := make([]byte, 0, len(s))

	for i := 0; i < len(s); i++ {
		c := s[i]
		if c == '(' || c == '[' || c == '{' {
			stack = append(stack, c)
			continue
		}

		if len(stack) == 0 {
			return false
		}
		top := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if c == ')' && top != '(' {
			return false
		}
		if c == ']' && top != '[' {
			return false
		}
		if c == '}' && top != '{' {
			return false
		}
	}

	return len(stack) == 0
}

相似题目

题目	难度	考察点
22. 括号生成	中等	回溯
32. 最长有效括号	困难	栈、DP
301. 删除无效的括号	困难	BFS、回溯
1003. 检查替换后的词是否有效	中等	栈
2116. 判断一个括号字符串是否有效	中等	贪心
2337. 移动片段得到字符串	中等	双指针
71. 简化路径	中等	栈
150. 逆波兰表达式求值	中等	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/07220011