32. 最长有效括号

原题地址：https://leetcode.cn/problems/longest-valid-parentheses/

题解

参考题解思路

设dp[i]是以s.charAt(i)结尾的最长连续有效括号

我们根据s.charAt(i)的不同分类讨论：

s.charAt(i)为’(‘时：
自然地，不存在以’(‘结尾的有效括号，所以此时dp[i]=0，即

s.charAt(i)为’)’时：

当s.charAt(i-1)为’(‘时：

i和i-1本身即为一段有效括号，假设i-1前有一段有效括号，则此时有

考虑到当i-1前无有效括号，则此时dp[i-2]=0，不妨碍结果的正确性

当s.charAt(i-1)同为’)’时：

我们认为i-1处的这个’)’是某段有效括号的一部分（且是结尾），而此时我们则需要找到这段有效括号的前一个字符，判断它是否为’(‘，即”(XXXXXX)”的情况，对于i-1，我们已经知道了以i-1结尾的有效括号长度为dp[i-1]，则这个左括号在且只能在(i-1)-dp[i-1]的位置。若为左括号，则说明[(i-1)-dp[i-1],i]同样为一段有效括号，且这段括号是在[(i-1)-dp[i-1]+1,i-1]的两端加上一对括号形成的
考虑到这段有效括号前面仍有可能有一段有效括号（如”()(XXXXXX)”），类似上一种情况，应当再加上dp[(i-1)-dp[i-1]-1]的值，则此时有

考虑到i-1处有效括号长度为0，则s.charAt((i-1)-dp[i-1])=='('的判断变为s.charAt(i-1)=='('的判断，同上一种情况
考虑到(i-1)-dp[i-1]前无有效括号，则此时dp[(i-1)-dp[i-1]-1]=0，不妨碍结果的正确性

无论是第二种情况下的dp[i-2]还是第三种情况下的dp[(i-1)-dp[i-1]-1]，都是我们已经得到了一段独立的有效括号，但是需要判断一下前面是否同样存在一段独立的有效括号可以结合，因此这两种情况还需要考虑到边界条件，即i-2<0和(i-1)-dp[i-1]-1<0的情况，这种情况下我们得到的独立有效括号是贴着边缘的，之前必然不再存在其他有效括号段

时间复杂度：O(N)

空间复杂度：O(N)

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

class Solution {
    fun longestValidParentheses(s: String): Int {
        if (s.length==0) return 0
        val dp=IntArray(s.length)
        var max=0
        for (i in 1 until s.length){
            if (s[i]=='(') {
                dp[i]=0
            } else if(s[i-1]=='('){
                dp[i]=(if(i-2>= 0) dp[i-2] else 0)+2
            } else if(i-1-dp[i-1]>=0&&s[i-1-dp[i-1] =='('){
                dp[i]=(if(i-1-dp[i-1]-1>=0) dp[i-1-dp[i-1]-1] else 0)+dp[i-1]+2
            }
            max=Math.max(max,dp[i])
        }
        return max
    }
}