LeetCode 32. 最长有效括号

Categories:

Tags:

题目描述
思路分析
1. 解法一：栈 + 基准下标（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 32. 最长有效括号

思路分析

解法一：栈 + 基准下标（推荐）

核心思路：

栈中存储”尚未被匹配的括号下标”，栈顶始终保存最后一个未匹配字符的位置，作为有效子串的左边界参考点。

初始化时压入 -1 作为基准，表示第一个有效子串从 index=0 开始前的边界。

遇到 '('：将当前下标入栈（等待未来右括号匹配）。

遇到 ')'：弹出栈顶尝试匹配一个左括号：

弹出后栈为空：说明这个右括号是多余的，没有左括号与之匹配，将当前下标压栈作为新基准。

弹出后栈不为空：匹配成功，以当前右括号结尾的最长有效子串长度 = i - stack.peek()。

关键点：栈顶是”最后一个未被匹配的字符”，它之后到 i 的所有括号都已完整匹配，所以长度就是 i - 栈顶。

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串长度，只需一次线性扫描

空间复杂度：O(n)，其中 n 为字符串长度，栈最坏情况下存储所有字符的下标

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 压入 -1 作为初始基准，方便计算第一个有效子串的长度
        stack.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 左括号下标入栈，等待匹配
                stack.push(i);
            } else {
                // 弹出栈顶，尝试匹配左括号
                stack.pop();
                if (stack.isEmpty()) {
                    // 栈空说明当前右括号无法匹配，将其下标作为新基准
                    stack.push(i);
                } else {
                    // 匹配成功，计算以当前位置结尾的有效子串长度
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}

func longestValidParentheses(s string) int {
	// 压入 -1 作为初始基准，方便计算第一个有效子串的长度
	stack := []int{-1}
	maxLen := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			// 左括号下标入栈，等待匹配
			stack = append(stack, i)
		} else {
			// 弹出栈顶，尝试匹配左括号
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				// 栈空说明当前右括号无法匹配，将其下标作为新基准
				stack = append(stack, i)
			} else {
				// 匹配成功，计算以当前位置结尾的有效子串长度
				length := i - stack[len(stack)-1]
				if length > maxLen {
					maxLen = length
				}
			}
		}
	}
	return maxLen
}

解法二：动态规划

核心思路：

定义 dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度。

只有 s[i] == ')' 时 dp[i] 才可能不为 0，分两种情况：

情况一：s[i-1] == '('，即 ...() 形式，dp[i] = dp[i-2] + 2。

情况二：s[i-1] == ')'，即 ...)) 形式，设 j = i - dp[i-1] - 1，若 s[j] == '('，则 dp[i] = dp[i-1] + 2 + dp[j-1]（需要将 j 之前相邻的有效子串也合并进来）。

最终答案为 dp 数组中的最大值。

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串长度，只需一次线性扫描

空间复杂度：O(n)，其中 n 为字符串长度，需要一个 dp 数组

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        // dp[i] 表示以 s[i] 结尾的最长有效括号子串长度
        int[] dp = new int[n];
        int maxLen = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // 情况一：s[i-1..i] 形如 "()"，拼接 i-2 之前的有效部分
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (dp[i - 1] > 0) {
                    // 情况二：s[i-1] 也是 ')'，跳过已匹配子串，找对应的左括号
                    int j = i - dp[i - 1] - 1;
                    if (j >= 0 && s.charAt(j) == '(') {
                        // 合并内层有效子串、当前匹配对，以及 j-1 之前的有效部分
                        dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
                    }
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
}

func longestValidParentheses(s string) int {
	n := len(s)
	// dp[i] 表示以 s[i] 结尾的最长有效括号子串长度
	dp := make([]int, n)
	maxLen := 0
	for i := 1; i < n; i++ {
		if s[i] == ')' {
			if s[i-1] == '(' {
				// 情况一：s[i-1..i] 形如 "()"，拼接 i-2 之前的有效部分
				if i >= 2 {
					dp[i] = dp[i-2] + 2
				} else {
					dp[i] = 2
				}
			} else if dp[i-1] > 0 {
				// 情况二：s[i-1] 也是 ')'，跳过已匹配子串，找对应的左括号
				j := i - dp[i-1] - 1
				if j >= 0 && s[j] == '(' {
					// 合并内层有效子串、当前匹配对，以及 j-1 之前的有效部分
					dp[i] = dp[i-1] + 2
					if j >= 1 {
						dp[i] += dp[j-1]
					}
				}
			}
			if dp[i] > maxLen {
				maxLen = dp[i]
			}
		}
	}
	return maxLen
}

相似题目

题目	难度	考察点
20. 有效的括号	简单	栈
22. 括号生成	中等	回溯
301. 删除无效的括号	困难	回溯、BFS
1249. 移除无效的括号	中等	栈
678. 有效的括号字符串	中等	栈、贪心
856. 括号的分数	中等	栈
921. 使括号有效的最少添加	中等	贪心、栈
84. 柱状图中最大的矩形	困难	单调栈
42. 接雨水	困难	栈、双指针

本文作者: HGNULB

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