给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses
方案1 栈
var longestValidParentheses1 = function (s) {
let stack = [];
let match = new Array(s.length).fill(0);
for (let i = 0; i < s.length; i++) {
if (s[i] === "(") {
stack.push(i);
} else {
if (stack.length) {
stack.pop();
} else {
match[i] = 1;
}
}
}
for (let i = 0; i < stack.length; i++) {
match[stack[i]] = 1;
}
let count = 0;
let max = 0;
for (let i = 0; i < match.length; i++) {
if (match[i] === 1) {
max = max > count ? max : count;
count = 0;
} else {
count++;
}
}
max = max > count ? max : count;
return max;
};
方案2 动态规划
var longestValidParentheses2 = function (s) {
if (s.length < 2) {
return 0;
}
// 定义 dt 数组，置0
let dt = new Array(s.length).fill(0);
for (let i = 1; i < s.length; i++) {
if (s[i] === ")") {
if (s[i - 1] === "(") {
// 示例： ()() [0, 2, 0, 4]
// 4 = dt[i - 2] + 2
dt[i] = (i >= 2 ? dt[i - 2] : 0) + 2;
} else if (i > dt[i - 1] && s[i - dt[i - 1] - 1] === "(") {
// (()) [0, 0, 2, ]
// 当i=3时： i - dt[i - 1] - 1 = 0; s[0] = (
// ()(()) [0, 2, 0, 0, 2, ]
// 当 i = 5时：(i - dt[i - 1] - 2 >= 0 ? dt[i - dt[i - 1] - 2] : 0)
// 前面还有连续未加入，则需要加入
dt[i] = dt[i - 1] + 2 + (i - dt[i - 1] - 2 >= 0 ? dt[i - dt[i - 1] - 2] : 0);
}
}
}
return Math.max(...dt);
};
