Problem: 32. 最长有效括号
思路
👨🏫 参考题解
文章来源：https://www.toymoban.com/news/detail-809157.html
Code
⏰ 时间复杂度:
O
(
n
)
O(n)
O(n)
🌎 空间复杂度:
O
(
n
)
O(n)
O(n)文章来源地址https://www.toymoban.com/news/detail-809157.html
class Solution {
public int longestValidParentheses(String s)
{
int n = s.length();
int[] f = new int[n];// f[i] 表示以第 i 个字符结尾的最长有效子字符串的长度
int ans = 0;
for (int i = 1; i < n; i++)
{
if (s.charAt(i) == ')')// 只有右括号结尾才有效
if (s.charAt(i - 1) == '(')// 上一个是 左括号
{
if (i < 2)
f[i] = 2;
else
f[i] = f[i - 2] + 2;
} else // 上一个也是 右括号
{
if (f[i - 1] > 0) //前面已经组成有效括号对序列
{
int pre = i - 1 - f[i - 1]; // 此处 s[pre] 与 s[i] 是相配对的位置
if (pre >= 0 && s.charAt(pre) == '(')// 存在且配对成功
{
f[i] = f[i - 1] + 2;// 在前边的 f[i-1] 上再加上一对
if (pre - 1 > 0)//看看 pre 前边是否还有已经配对好的序列
f[i] += f[pre - 1];
}
}
}
ans = Math.max(ans, f[i]);//更新答案
}
return ans;
}
}
到了这里，关于力扣hot100 最长有效括号 动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
