leetcode-32. 最长有效括号

题目：最长有效括号

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”

输出: 2

解释: 最长有效括号子串为 “()”

示例 2:

输入: “)()())”

输出: 4

解释: 最长有效括号子串为 “()()”

解析：

注意题目要求是子串，子串指的是一段连续的字符串，中间不能有隔断。

看到这个题目，最直接的办法是暴力搜索，遍历每个子串，判断其是否是有效的，然后找到最长的子串，时间复杂度为O(n^3)。

感觉这个时间复杂度有点高，应该还有更简单的算法，于是经过一番思索，我发现，如果以输入字符串s的第i个字符为起点，最长的有效子串存在如下公式：

1. 如果s[i]=(，s[i+1]=)，那么最长有效子串的长度为2+n[i+2]，其中n是一个数组，表示以当前字符为起点，最长的有效子串长度；
2. 如果s[i]=(，而s[i+1]!=)，那么有可能存在一个以s[i+1]为起点的有效子串包裹在s[i]和后面与s[i]相对应的“)”里面，比如：(()())，中间的“()()”包裹在最外层括号的里面，那么此时最长有效子串长度为2+n[i+1]，这里还需要考虑另外一种情况，如果与s[i]相对应的“)”后面还有一个有效子串，那么这时最长有效子串长度便为2+n[i+1]+n[i+2+ n[i+1] ]，这个公式有点复杂，请看下图：

   

   在i+5的后面还有一个长度为2的有效子串，那么n[i]=2+n[i+1]+n[i+6]=2+4+2=8。

根据上面的公式，倒序遍历字符串即可找到最长的有效子串，时间复杂度为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;
    }
           

运行结果为：