需要在每一个右括号处判断是否有可以闭合的左括号

最长有效括号

描述

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

解法 动态规划

遍历字符串时只需要判断右括号的情况

1. 前一个字符就是左括号，无嵌套的括号
   长度直接加2，如果左括号前面一个字符存在，则加上它存的有效长度

   if(s[i-1] === '(') {
     dp[i] = 2 + (dp[i - 2] >= 0 ? dp[i - 2] : 0)
   }
   

2. 前一个字符不是左括号，是在嵌套的括号里
   则通过前一个储存的长度得到它的左括号，再判断前一个字符是不是左括号。
   dp[i - 1] 前一个存储的值
   s[i - dp[i - 1] - 1] === '(' 前一个合法字符的前一个括号是否是左括号，是的话就可以闭合，对应 (()) 这种情况
   由于前一个字符存储的长度是嵌套括号里的长度，算完之后还需要判断再加上括号外前一个字符的有效长度dp[i - dp[i - 1] - 2]。对应 ()(())

   (	)	(	(	)	)
   0	2	0	0	2	6

   if (s[i - dp[i - 1] - 1] === '(') {
      dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] || 0) + 2
   }
   

完整代码

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
    if (s.length < 2) {
        return 0
    }
    let dp = Array(s.length).fill(0), i = 0, j = 0, maxlength = 0
    for (i = 1; i < s.length; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                dp[i] = 2 + (dp[i - 2] || 0)
            } else if (s[i - dp[i - 1] - 1] === '(') {
                dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] || 0) + 2
            }
            maxlength = Math.max(dp[i], maxlength)
        }
    }
    return maxlength
};