【力扣100题】50.最长有效括号

题目描述

给你一个只包含'('和')'的字符串，找出其中最长有效（格式正确且连续）括号子串的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，例如"(()())"。

示例：

• 输入：s = "(()"→ 输出：2（最长有效括号子串是"()")
• 输入：s = ")()())"→ 输出：4（最长有效括号子串是"()()")
• 输入：s = ""→ 输出：0

解题思路总览

本题采用动态规划方法。

完整代码

classSolution{public:intlongestValidParentheses(string s){intmaxLen=0,n=s.size();vector<int>dp(n,0);for(inti=1;i<n;i++){if(s[i]==')'){if(s[i-1]=='('){dp[i]=(i>=2?dp[i-2]:0)+2;}elseif(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='('){dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;}maxLen=max(maxLen,dp[i]);}}returnmaxLen;}};

算法流程图

输入: s = ")()())" 初始化: n = 6 dp[0...5] = 0 maxLen = 0 i = 1, s[1] = '(': s[1] == ')'? 否，跳过 maxLen = 0 i = 2, s[2] = ')': s[2] == ')'? 是 s[1] == '('? 是！ dp[2] = dp[0] + 2 = 0 + 2 = 2 maxLen = max(0, 2) = 2 i = 3, s[3] = '(': s[3] == ')'? 否，跳过 maxLen = 2 i = 4, s[4] = ')': s[4] == ')'? 是 s[3] == '('? 是！ dp[4] = dp[2] + 2 = 2 + 2 = 4 maxLen = max(2, 4) = 4 i = 5, s[5] = ')': s[5] == ')'? 是 s[4] == '('? 否，进入 else if i - dp[4] = 5 - 4 = 1 > 0 s[1] = '('? 是！ dp[5] = dp[4] + dp[0] + 2 = 4 + 0 + 2 = 6 maxLen = max(4, 6) = 6 最终 maxLen = 6 输出: 6

逐行解析

intmaxLen=0,n=s.size();

含义：maxLen记录全局最长有效括号长度，n记录字符串长度。

vector<int>dp(n,0);

含义：dp[i]表示以第i个字符结尾的最长有效括号子串长度。初始化为 0。

for(inti=1;i<n;i++)

含义：从索引 1 开始遍历（因为 dp[0] 只能是 0，不需要计算）。

if(s[i]==')')

含义：只有当当前字符是)时才可能形成有效括号。

if(s[i-1]=='(')

含义：情况一："..."形式的最近匹配。例如"()"或"(...)()"

dp[i]=(i>=2?dp[i-2]:0)+2;

含义：如果是"()"形式，长度为 2 加上 dp[i-2]（之前已匹配的长度）。需要判断 i-2 是否 >= 0。

elseif(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='(')

含义：情况二：类似"(...])"的形式，其中...已经是有效括号段。例如"(())"中 s[3]=‘)’ 时，i-dp[i-1]=3-2=1，s[0]=‘(’，形成匹配。

dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;

含义：

• dp[i - 1]：之前已经匹配的有效括号长度
• ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0)：加上再之前的有效括号长度
• + 2：加上当前匹配的"()"

maxLen=max(maxLen,dp[i]);

含义：更新全局最长长度。

状态转移图解

情况一："()" 形式 i-1 i '(' ')' dp[i] = dp[i-2] + 2 情况二："(...])" 形式 i-1 i "... ( ... ) )" ^dp[i-1] ^ i - dp[i-1] - 1 (与 i 配对的 '(' 的位置) dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2

复杂度分析

面试追问 FAQ

相关题目

总结