最长有效括号

来源Leetcode第32题最长有效括号

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

示例 2:

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

Wrong Answer

一开始看到这题，我是用的栈写的，通过判断栈顶元素和入栈元素是否匹配，如果匹配则长度+2，不匹配则重新初始化长度，然而这样会有个问题，对于形如”()(()”这样的组合，我的输出是4，然而预期应该是2，其实还是因为算法不够完善。

思考了一番，既然如此，那我就对每一个可能的子串组合进行统计，记录所有子串里最长的有效括号，然而这在第227/230个算例时，发生了TLE,T T，先附上没有AC的代码吧：

public int isLegal(String s) {
    // 空字符串
    if (s.length() == 0)
        return 0;
    // 栈元素个数
    int index = 0;
    // 栈
    char[] stack = new char[s.length()];
    for (int i = 0; i < s.length(); i++) {
        switch (s.charAt(i)) {
            case '(':
                // 进栈
                stack[index++] = s.charAt(i);
                continue;
            case ')':
                if (index == 0 || stack[index - 1] != '(')
                {
                    return 0;
                }
                if(stack[index - 1] == '('){
                    index--;
                    continue;
                }
                // stack[--index] == '(' ，才会contniue
                // --index：相当于满足的元素出栈
        }
    }
     return index == 0 ?  1 :  0;
}

public int longestValidParentheses(String s) {
    int maxlength = 0;
    for(int i = 0 ;i < s.length();i++){
        for(int j = i + 2;j<=s.length();j+=2){
            if(isLegal(s.substring(i,j)) == 1){
                maxlength = Math.max(maxlength , j - i);
            }
        }
    }
    return maxlength;
}

栈

在查看题解时，我看到了一篇也是用栈写的，不过答主是用了下标入栈，通过判断出栈元素之间的距离来判断最长的有效括号长度。

我们扫描到左括号，就将当前位置入栈。

扫描到右括号，就将栈顶出栈（代表栈顶的左括号匹配到了右括号），然后分两种情况。

• 栈不空，那么就用当前的位置减去栈顶的存的位置，然后就得到当前合法序列的长度，然后更新一下最长长度。

• 栈是空的，说明之前没有与之匹配的左括号，那么就将当前的位置入栈。

代码如下:

public int longestValidParentheses(String s) {
    int maxans = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.empty()) {
                stack.push(i);
            } else {
                maxans = Math.max(maxans, i - stack.peek());
            }
        }
    }
    return maxans;
}    

依次比对

此外，我们可以判断从每个位置开始的最长合法子串是多长即可。而判断是否是合法子串，我们不用栈，而是用一个变量记录当前的括号情况，遇到左括号加 1，遇到右括号减 1，如果变成 0 ，我们就更新下最长合法子串。

代码如下：

public int longestValidParentheses(String s) {
    int count = 0;
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        count = 0;
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(j) == '(') {
                count++;
            } else {
                count--;
            }
            //count < 0 说明右括号多了，此时无论后边是什么，一定是非法字符串了，所以可以提前结束循环
            if (count < 0) {
                break;

            }
            //当前是合法序列，更新最长长度
            if (count == 0) {
                if (j - i + 1 > max) {
                    max = j - i + 1;
                }
            }
        }
    }
    return max;
}

动态规划

接下来就是官方题解里提到的动态规划
dp[i] 代表以下标 i 结尾的合法序列的最长长度，
我们来分析下 dp 的规律。

首先我们初始化所有的 dp 都等于零。
以左括号结尾的字符串一定是非法序列，所以 dp 是零，不用更改。
以右括号结尾的字符串分两种情况。

• 右括号前边是 ( ，类似于 ……（）。
  dp[i] = dp[i-2] + 2 （前一个合法序列的长度，加上当前新增的长度 2）
• 右括号前边是 )，类似于 ……））。
  此时我们需要判断 i-dp[i-1]-1 （前一个合法序列的前边一个位置） 是不是左括号。
  如果是左括号，此时dp[i] = dp[i-1]+dp[i-dp[i -1]-2]+2 （当前位置的前一个合法序列的长度，加上匹配的左括号前边的合法序列的长度，加上新增的长度 2）
  如果不是左括号，那么此时位置 的右括号没有匹配的左括号，所以 dp[i] = 0 ，不需要更新。

代码如下：

public int longestValidParentheses(String s) {
    int maxans = 0;
    int dp[] = new int[s.length()];
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            //右括号前边是左括号
            if (s.charAt(i - 1) == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            //右括号前边是右括号，并且除去前边的合法序列的前边是左括号
            } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxans = Math.max(maxans, dp[i]);
        }
    }
    return maxans;
}

两次遍历

当然还有一种很神奇的解法：
从左到右扫描，用两个变量 left 和 right 保存的当前的左括号和右括号的个数，都初始化为 0 。

• 如果左括号个数等于右括号个数了，那么就更新合法序列的最长长度。
• 如果左括号个数大于右括号个数了，那么就接着向右边扫描。
• 如果左括号数目小于右括号个数了，那么后边无论是什么，此时都不可能是合法序列了，此时 left 和 right 归 0，然后接着扫描。

从左到右扫描完毕后，同样的方法从右到左再来一次，因为类似这样的情况 ( ( ( ) ) ，如果从左到右扫描到最后，left = 3，right = 2，期间不会出现 left == right。但是如果从右向左扫描，扫描到倒数第二个位置的时候，就会出现 left = 2，right = 2 ，就会得到一种合法序列。

代码如下：

public int longestValidParentheses(String s) {
    int left = 0, right = 0, maxlength = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            maxlength = Math.max(maxlength, 2 * right);
        } else if (right >= left) {
            left = right = 0;
        }
    }
    left = right = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            maxlength = Math.max(maxlength, 2 * left);
        } else if (left >= right) {
            left = right = 0;
        }
    }
    return maxlength;
}