题目

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

let s = ")()(())(()"; let dp = []; //存的是有效字符长度 let maxLen = 0; let stack = []; //栈，存储还没有被匹配的'('的索引 for (let i = 0; i < s.length; i++) { if (stack.length && s[i]===")"){ /* 1 遍历到的是')' 且当前的栈里面没有能匹配的'(' 把索引和 从匹配到的'('到遍历到的')' 的长度（ i-stack[stack.length-1]+1 ）push到dp中 */ let temp = { index:i, len:i-stack[stack.length-1]+1 }; /* 1 如果匹配的'('的有前一个元素 就把这个前一个对应的dp值加到当前遍历的')'的dp中（ += dp[temp.index-temp.len].len ） */ dp.push(temp); if (temp.index-temp.len>=0){ // dp[i - (i - stack[stack.length - 1] + 1) - 1].len temp.len += dp[temp.index-temp.len].len; } dp[dp.length-1].len=temp.len; if (temp.len){ maxLen = Math.max(maxLen,temp.len) } stack.pop(); }else { /* 1 遍历到的是')' 且当前的栈里面没有能匹配的‘(’ 2 遍历到的是'(' 把当前的索引和 0 push到dp中 */ let temp = { index:i, len:0 }; dp.push(temp); if (s[i]==="("){ stack.push(i); } } } return maxLen

最后dp：

[ { index: 0, len: 0 }, { index: 1, len: 0 }, { index: 2, len: 2 }, { index: 3, len: 0 }, { index: 4, len: 0 }, { index: 5, len: 2 }, { index: 6, len: 6 }, /* 这里的原本是 4（stack里存的最后一个'('的索引是 3 到当前索引为 6 ） 然后加上索引 6 减去长度 4 对应{ index: 2, len: 2 }的 len 是 2 最后就为 6 */ { index: 7, len: 0 }, { index: 8, len: 0 }, { index: 9, len: 2 } ]