leetcode hot 100-32. 最长有效括号

32. 最长有效括号

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

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

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

思路一：借助栈

思路和leetcode hot 100-20. 有效的括号这题类似，只不过是在判断匹配的时候需要出栈后当前字符下标和栈顶元素下标做差得到一个匹配括号长度，然后更新最大值

class Solution {
    public int longestValidParentheses(String s) {

        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        int len = s.length();
        // 把遇到的所有左括号的下标都存入栈中
        for(int i = 0; i < len; i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }else{
                 // 如果碰到右括号，判断栈顶下标对应的字符是否是左括号，如果是，说明匹配，
                 // 出栈，与栈顶元素做差，否则直接入栈
                if(!stack.isEmpty() && s.charAt(stack.peek()) == '('){
                    stack.pop();
                    int peek = stack.isEmpty() ? -1 : stack.peek(); // 栈为空则返回-1
                    max = Math.max(max, i - peek);
                }else{
                    stack.push(i);
                }
            }
        }
        return max;       
    }
}

leetcode 执行用时：3 ms > 53.72%, 内存消耗：38.5 MB > 82.48%

复杂度分析：

时间复杂度：O(n)。只遍历了一次字符串，所以时间复杂度为O(n)。

空间复杂度：O(n)。栈的大小即为空间复杂度的主要来源，最坏情况下，即当所有字符均为左括号时，所有字符均需入栈，这时栈的大小为 n, 所以空间复杂度为O(n)。

思路二：动态规划

思路参考：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

定义一个dp[]数组，dp[i]表示以第i个字符结尾的子串的最长有效括号长度，初始时所有长度都是0，需要求出以每个字符结尾的最长有效括号长度dp[i]

注意到如果第i个字符为左括号，那以第i个字符结尾的最长有效括号长度肯定等于0， 所以dp[i] = 0， 所以相当于遇到左括号可以不用求dp[i]， 

现在只需要求当第 i 个字符为右括号时的dp[i], 分成两种情况

• 当第 (i-1)个字符为左括号时，即为 “..()”时， 第 （i-1）字符和第 i 个字符形成一个有效括号对，那么dp[i] = dp[i-2] + 2;
• 当第(i-1)个字符为右括号时，即为 "...))" 时， 需要判断与第 i 字符相对的那个字符 (第 i - dp[i-1] - 1个字符) 是否是左括号，如果是，等于dp[i-1] + 2, 否则等于0;

其实上面的状态转移方程是有问题的，比如遇到 "()(())" 这种情况，期望结果是6，但实际输出是4

所以应该将上面的状态转移方程进行改进，

当第(i-1)个字符为右括号时，即为 "...))" 时， 需要判断与第 i 字符相对的那个字符 (第 i - dp[i-1] - 1个字符) 是否是左括号，如果是，那么等于第 i-dp[i-1] - 2 个字符为结尾的子串最大有效括号长度加上 dp[i-1] 的长度再加2， 即等于dp[i-dp[i-1] - 2] + dp[i-1] + 2, 否则等于0;

class Solution {
    public int longestValidParentheses(String s) {

        int len = s.length();
        int[] dp = new int[len];
        int max = 0;
        for(int i  = 1; i < len; 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] - 1 >= 0 && s.charAt(i - dp[i-1] - 1) == '('){
                        dp[i] = dp[i-1] + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0) + 2;
                    }
                }
                max = Math.max(dp[i], max);
            }
        }
        return max;
    }
}

leetcode 执行用时：1 ms > 100.00%, 内存消耗：38.5 MB > 84.49%

复杂度分析：

时间复杂度：O(n)。遍历了整个字符串，所以时间复杂度为O(n)。

空间复杂度：O(n)。需要一个大小为 n 的 辅助dp[]数组，所以空间复杂度为O(n)。

思路三：双指针法

遇到左括号，左括号数 left 加一，遇到右括号，右括号数 right 加一

如果右括号数大于左括号数，左右括号计数器都置为0，重新开始计数

如果左右括号数相等，将最大值与 2*left 比较，更新最大值

后面还需要逆序来一遍，因为 (() 或者 (()() 这样的情况，在正序遍历的时候是统计不到的，但是注意在逆序的过程中，

如果左括号数大于右括号数，说明前面的括号已经不合法了，重新计数，因为逆序遍历了嘛

class Solution {
    public int longestValidParentheses(String s) {

        int left = 0, right = 0;
        int len = s.length();
        int max = 0;
        for(int i = 0; i < len; i++){
            if(s.charAt(i) == '('){
                left++;
            }else{
                right++;
            }
            if(right > left){
                left = right = 0;   // 如果右括号数大于左括号数，说明前面的括号已经不合法了，重新计数
            }else if(right == left){
                max = Math.max(max, 2 * left);
            }
        }
        // 逆序来一遍，因为(()或者(()()这样的情况，在正序遍历的时候是统计不到的
        left = right = 0;
        for(int i = len - 1; i >= 0; i--){
            if(s.charAt(i) == '('){
                left++;
            }else{
                right++;
            }

            if(left > right){
                left = right = 0;   // // 如果左括号数大于右括号数，说明前面的括号已经不合法了，重新计数
            }else if(left == right){
                max = Math.max(max, 2 * left);
            }
        }
        return max;
    }
}

leetcode 执行用时：2 ms > 79.09%, 内存消耗：38.3 MB > 88.76%

复杂度分析：

时间复杂度：O(2n)。遍历了两次字符串，所以时间复杂度为O(2n)。

空间复杂度：O(n)。只需要常数个变量的空间，所以空间复杂度为O(n)。