最长有效括号

Question

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

示例 1

输入: (() 输出: 2 解释: 最长有效括号子串为 ()

示例 2

输入: )()()) 输出: 4 解释: 最长有效括号子串为 ()()

function longestValidParentheses(s) {
    let stack = [-1],
        maxLen = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.length == 0) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }
    return maxLen;
};

console.log(longestValidParentheses(")()())"))

使用栈来维护左右括号的匹配关系，遍历字符串，当遇到左括号时将其下标入栈，当遇到右括号时弹出栈顶元素表示匹配成功，此时更新最长有效括号的长度，如果栈为空，则说明当前右括号没有匹配成功，需要将当前右括号的下标入栈，最后根据栈中元素的下标计算最长有效括号的长度。