32.最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

**输入：** s = "(()"
**输出：** 2
**解释：** 最长有效括号子串是 "()"

示例 2：

**输入：** s = ")()())"
**输出：** 4
**解释：** 最长有效括号子串是 "()()"

示例 3：

**输入：** s = ""
**输出：** 0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

思路一：用栈遍历匹配括号，并记录下匹配的位置，将匹配的位置排序，找出最长的，时间复杂度nlogn

思路二：原地修改s，将匹配到的括号去掉或者做标记，遍历找出最长的

思路三：动态规划：定义dp[i] 表示以下标 i (包括i)字符结尾的有效括号的长度

​ 当s[i]为（时，dp[i]=0

​ 当s[i]为），s[i-1]为（时，dp[i]=dp[i-2]+2

​ 当s[i]为），s[i-1-dp[i-1]]为（时，dp[i]=dp[i-1]+2+temp

class Solution {
    public int longestValidParentheses(String s) {
        int[] dp=new int[s.length()];
        int ans=0;
        //直接从i=1判断
        for(int i=1;i<s.length();i++)
        {
            if(s.charAt(i)=='(')   //左括号
                dp[i]=0;
            else    //右括号
            {
                if(s.charAt(i-1)=='(')   //前一位为左括号（，正好匹配，直接+2
                    dp[i]=i<2?2:dp[i-2]+2;
                else if((i-1-dp[i-1])>=0 && s.charAt(i-1-dp[i-1])=='('){  //else前一位(i-1)为右括号)，寻找前方匹配的(，i-1再减去dp[i-1]的长度
                    int temp=(i-2-dp[i-1])>=0?dp[i-2-dp[i-1]]:0;   //()(()),定义temp因为计算完(())长度，前面还需要加上()长度，i-1-dp[i-1]再-1
                    dp[i]=dp[i-1]+2+temp;
                }
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}