NO.32 最长有效括号困难

思路一：暴力法 遍历所有偶数长度的子串，得到最长的有效括号序列。但是此方法会超时。

public int longestValidParentheses(String s) {
    if (s==null||s.equals(""))return 0;
    int maxLen=0;
    //遍历所有子串
    for (int i = 0; i < s.length(); i++) {
        //只要偶数长度的，奇数长度一定无效
        for (int j=i+2;j<=s.length();j++){
            if (isValid(s.substring(i,j))){
                maxLen=Math.max(maxLen,j-i);
            }
        }
    }
    return maxLen;
}
//判断括号序列是否有效
private boolean isValid(String s) {
    Stack<Character> stack=new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i)=='('){
            stack.push('(');
        }else if (stack.size()>0){
            stack.pop();
        }else {
            return false;
        }
    }
    return stack.isEmpty();
}

时间复杂度：O(n^3)

思路二：优化暴力法 简单的优化上面的方法，暴力法会有很多可以避免的判断，例如我们判断下标为0长度是2的序列是有效的，接下来判断长度为4、为6。。。的序列的时候，依然要从0开始判断，实际上并不需要，因为每个序列的前一个序列已经判断过之前的部分是有效的了。

因为题目中说只有’(‘和’)’两种字符，所以我们用1表示’(‘、用-1表示’)’。用count记录每个序列的和，如果小于0则说明’)’过多了当前序列无效，如果最终count等于0，则说明当前序列有效，更新有效序列长度。

public int longestValidParentheses(String s) {
    if (s==null||s.equals(""))return 0;
    int maxLen=0;
    //遍历所有子串
    for (int i = 0; i < s.length(); i++) {
        int count=0;
        for (int j=i;j<s.length();j++){
            // ( +1,) -1
            if (s.charAt(j)=='(')count++;
            else count--;
            //小于0说明 )比(多，无效序列
            if (count<0)break;
            //有效序列，更新maxLen
            if (count==0)maxLen=Math.max(maxLen,j-i+1);
        }
    }
    return maxLen;
}

时间复杂度：O(n^2)

思路三：动态规划 dp数组的含义：dp[i]以下标为i结尾的有效序列的最大长度。

初始化：dp数组元素都初始化为0。

填写dp数组，状态转移方程：

如果i是’(‘，以左括号结尾的序列一定是无效序列，所以依然为0。
如果i是’)’，以有括号结尾的序列分两种情况：
- 如果i-1是’(‘，组成形如”()”。dp[i]=dp[i-2]+2，意思是在前一个有效序列的长度基础上加上当前结尾长度为2的”()”。
  
  例如，dp[2]=dp[2-2]+2=2、dp[4]=dp[4-2]+2=4
- 如果i-1是’)’，组成形如”))”。需要检查i-dp[i-1]-1是否为’(‘，意思是检查i的前一个有效序列之前是否为’(‘。如果是左括号，则可以和i组成”()”，则dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2意思是i之前的有效序列长度加上与i进行匹配的左括号前面的有效序列长度加上新增的序列长度2。如果不是左括号，则无法与i进行匹配，即当前i结尾的是无效序列，依然为0。
  
  例如，dp[6]=dp[6-1]+dp[6-dp[6-1]-2]+2=6

==实现的时候要注意判断下标越界。==

public int longestValidParentheses(String s) {
    if (s==null||s.equals(""))return 0;
    int maxLen=0;
    int[] dp=new int[s.length()];
    //遍历每个字符并填写dp数组
    for (int i=1;i<s.length();i++){
        //如果i是')'，分两种情况
        if (s.charAt(i)==')'){
            //情况一，i-1是'('。则可以和i有效组合。
            if (s.charAt(i-1)=='('){
                if (i-2>=0) dp[i]=dp[i-2]+2;
                else dp[i]=2;
            }else {//情况二，i-1是')'
                //如果i之前的有效序列之前是个左括号，则可以和i有效组合。否则i结尾的序列无效
                if (i-dp[i-1]-1>=0&&s.charAt(i-dp[i-1]-1)=='('){
                    if (i-dp[i-1]-2>=0)dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2;
                    else dp[i]=dp[i-1]+2;
                }
            }
        }
        //更新maxLen
        maxLen=Math.max(maxLen,dp[i]);
    }
    return maxLen;
}

时间复杂度：O(n) 大量的if else可以用三元运算符优化。

空间复杂度：O(n)

思路四：两次遍历 到这里，这个找最长有效括号的算法已经从n^3优化到了n。但是通过学习大佬的题解，发现另一种解法，时间复杂度是O(n)的同时将空间复杂度降至了常数。

先顺序扫描一遍，同时用left和right保存左右括号的个数：

如果left>right，则继续扫描。
如果left<right，则一定是无效序列，归零left、right。
如果left==right，则是有效序列，更新maxLen。

归零left、right。再逆序扫描一遍，同样的校验方法(逆序遍历则是left>right无效)。

最终得到maxLen。

public int longestValidParentheses(String s) {
    if (s==null||s.equals(""))return 0;
    int left=0,right=0,maxLen=0;
    //正序遍历
    for (int i = 0; i < s.length(); i++) {
        //统计左右括号数量
        if (s.charAt(i)==')'){
            right++;
        }else {
            left++;
        }
        //左右括号数量相等，则有效序列，更新maxLen
        if (left==right){
            maxLen=Math.max(maxLen,right+left);
        }else if (left<right){//右括号多于左括号，无效序列，重置计数
            left=0;
            right=0;
        }
    }
    left=0;
    right=0;
    //逆序遍历
    for (int i = s.length()-1; i >= 0; i--) {
        //统计数量
        if (s.charAt(i)==')'){
            right++;
        }else {
            left++;
        }
        //如果左右括号数量相等，有效序列，更新maxLen
        if (left==right){
            maxLen=Math.max(maxLen,right+left);
        }else if (left>right){//如果左括号多于有括号，无效序列，重置计数
            left=0;
            right=0;
        }
    }
    return maxLen;
}

时间复杂度：O(n)

空间复杂度：O(1)

最开始很迷惑为什么两次遍历可以得到正确的maxLen，后来在纸上写了几种不同情况的括号序列模拟了一下，不由得感叹：妙啊！牛逼的算法就是简单！有效！

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.32 最长有效括号 困难

NO.32 最长有效括号困难