32. 最长有效括号

题目链接：https://leetcode-cn.com/problems/longest-valid-parentheses/

难度：困难

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

示例 1:

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

示例 2:

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

解法一：暴力法

根据题目意思，我们需要找到最长的包含有效括号的子串的长度，那么意味着，我们的最长子串不一定是原字符串的首元素开始的。

但是如果我们的最长子串都是从首元素开始的，那么这道题就会变得非常简单。我们只需要利用一个循环，挨个从0，1，……为首元素，开始截取字符串，然后在判断这个子串的最长有效长度，最后拿出最大值即可。

如何判断计算一个字符串从首元素开始的最长有效长度？

我们可以利用栈的思想，但是没必要使用栈数据结构，利用一个int变量temp（初始值为0）就可以代替：

（1）我们遍历字符串，若遇到 ' ( ' 就给temp++；若遇到 ' ) ' 就给temp--;

（2）若遇到 temp = 0,说明前面的字符串刚好满足条件，我们可以更新当前这次遍历的最大长度maxLen = i +1;

（3）若遇到 temp < 0,说明前面的字符串已经不满足条件了，就可以直接return maxLen。

优化：

我们既然要先遍历截取子串，那么' ) '开始的子串一定是不满足条件的，可以直接跳过。

该方法用时是非常高的，在死亡的边缘徘徊！！！

代码：

public class Solution {
    public int longestValidParentheses(String s) {
        int result = 0;
        if(s.length()==0 && s.length()==1) {
            return 0;
        }
        for(int i = 0;i<s.length();i++) {
            if(s.charAt(i) == ')') {
                continue;
            }
            int maxLen = maxValid(s.substring(i));
            if(result < maxLen) {
                result = maxLen;
            }
        }   
        return result;
    }
    
    //计算从字符串串首开始计算最长有效的子串长度
    public int maxValid(String s) {
        int temp = 0;
        int maxLen = 0;
        for(int i = 0;i<s.length();i++) {
            if(s.charAt(i) == '(') {
                temp ++;
                
            }else {
                temp --;
                if(temp<0) {
                    return maxLen;
                }
                if(temp == 0) {
                    maxLen = i+1;
                }
            }
        }
        return maxLen;
    }
}

复杂度分析：

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

解法二：动态规划法

这道问题可以使用动态规划法，问题要求的是s[0,length-1]的最长有效子串长度，我们可以用dt[length]数组来统计，dt[]数组的默认值为0，dt[i]表示以i元素结尾的最长子串长度，那么s[i]一定为 ')' 。

在统计过程中，会出现如下几种情况：

（1）当 s[i]== ')'，s[i-1] =='('时，例如："……()"，符合条件，我们只需要更新dt[i] = dt[i-2] +2，当然如果 i-2<0的话，直接赋值dt[i]=2；

（2）当s[i] == ')'，s[i-1] == ')'时，例如："……))"，如果s[i-dt[i-1]-1] = '('，

那么

解释：

如果最后一个元素为' ) '是有效子串的一部分，那么他一定有一个对应的' ( ' 在倒数第二个 ')' 所在的有效子字符串的前面，如图所示：

代码：

public class Solution {
    public int longestValidParentheses(String s) {
        if(s.length()==0 || s.length()==1) {
            return 0;
        }
        int[] dt = new int[s.length()];
        int result = 0;
        for(int i = 1;i<s.length();i++) {
            if(s.charAt(i)==')') {
                if(s.charAt(i-1)=='(') {
                    dt[i] = (i>=2?dt[i-2]:0) + 2;
                }else if(i>dt[i-1] && s.charAt(i-dt[i-1]-1)=='(' ){
                    dt[i] = dt[i-1] + 2 + ((i-dt[i-1]-2)>=0?dt[i-dt[i-1]-2]:0);
                }
            }
            result = Math.max(result, dt[i]);
        }
        return result;
    }
}    

复杂度分析：

• 时间复杂度： O(n)
• 空间复杂度： O(n)

解法三：栈操作

算法思路：

我们利用一个栈，里面先存入一个-1，方便后面计算有效子串长度，我们栈中的栈首元素是为后面计算有效长度做标记。

遍历字符串，

• 若遇到'('，就把下标入栈；
• 若遇到')'，就出栈；
  • 若栈为空，说明该子串无效，因为我们的栈首存放的是标记位，并非'('的下标，那么我们就把当前的i入栈，作为新子串的标记位；
  • 若栈不为空，说明该字串有效，那么更新最长子串长度result = Math.max(result, i-stack.peek());

该算法的巧妙之处，正是栈首存放的是标记位，而非记录'('的下标。

代码：

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

复杂度分析：

• 时间复杂度： O(n)
• 空间复杂度： O(n)