当前位置 博文首页 > 龚厂长的博客：leetcode-32. 最长有效括号
题目：最长有效括号
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:
输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”
解析：
注意题目要求是子串，子串指的是一段连续的字符串，中间不能有隔断。
看到这个题目，最直接的办法是暴力搜索，遍历每个子串，判断其是否是有效的，然后找到最长的子串，时间复杂度为O(n^3)。
感觉这个时间复杂度有点高，应该还有更简单的算法，于是经过一番思索，我发现，如果以输入字符串s的第i个字符为起点，最长的有效子串存在如下公式：
根据上面的公式，倒序遍历字符串即可找到最长的有效子串，时间复杂度为O(n)。
下面上代码：
public int longestValidParentheses(String s) {
int len=s.length();
int n[]=new int[len];//数组n表示以当前字符为起点，最长的有效子串长度
byte[] chs=s.getBytes();
int res=0;//最长的有效子串长度
//倒序遍历字符串
for (int i = len - 2; i >= 0; i--) {
if (chs[i] == '(' && chs[i + 1] == ')') {
n[i]=2;
if(i+2<len && n[i+2]!=0){
n[i]+=n[i+2];
}
}else if(n[i+1]!=0 &&n[i+1]+i+1<len&& chs[i] == '(' && chs[n[i+1]+i+1]==')'){
int t=n[i+1]+i+2;
n[i] = n[i + 1] + 2;
if(t<len&&n[t]!=0){
n[i]+=n[t];
}
}
if(res<n[i]){
res=n[i];
}
}
return res;
}
运行结果为：
