最长有效括号

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例1：

输入：s = “(()” 输出：2 解释：最长有效括号子串是 “()”

示例2：

输入：s = “)()())” 输出：4 解释：最长有效括号子串是 “()()”

示例3：

输入：s = “” 输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 ‘(‘ 或 ‘)’

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

动态规划

function longestValidParentheses(s: string): number {
    if (!s || s.length < 2) return 0;
    const n = s.length;
    const dp: Array<number> = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        const char = s.charAt(i);
        const lastChar = s.charAt(i - 1);
        if (char === ')') {
            // 字符串形如"......()"
            if (lastChar === '(') {
                dp[i] = i === 1 ? 2 : dp[i -2] + 2;
            } else {
                const lastLength = dp[i - 1];
                // 字符串形如"......))"
                if (s[i - lastLength - 1] === '(') {
                    dp[i] = i -lastLength - 2 > 0 ? lastLength + dp[i - lastLength - 2] + 2 : lastLength + 2;
                }
            }
        }
    }
    return Math.max(...dp);
};

时间复杂度：O(n)
空间复杂度：O(n)

栈

可以观看 题解中的官方视频：https://leetcode.cn/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/#comment

function longestValidParentheses(s: string): number {
    if (!s || s.length < 2) return 0;
    const n = s.length;
    let maxValidLength = 0;
    // stack 记录 startIndex - 1
    // 此时最后一个没被匹配的右括号的下标为-1，方便后面根据 i - stack[lastIndex] 计算最大长度
    // startIndex - 1, 为了方便通过 i - 这个值 =  截取的长度，而无需再-1
    const stack: Array<number> = [-1];
    for (let i = 0; i < n; i++) {
        const char = s.charAt(i);
        if (char === '(') {
            // 记录startIndex
            stack.push(i);
        } else {
            // 弹出与之匹配的startIndex
            stack.pop()
            if (stack.length === 0) {
                // 记录最后一个没有被匹配的右括号下标 为 startIndex - 1
                stack.push(i);
            } else {
                // 有匹配的()，可以计算其长度，使用 i - 最后一个没有被匹配的右括号下标
                maxValidLength = Math.max(maxValidLength, i - stack[stack.length - 1]);
            }
        }
    }
    return maxValidLength;
};

时间复杂度：O(n)
空间复杂度：O(n)

计数器

function longestValidParentheses(s: string): number {
    if (!s || s.length < 2) return 0;
    const n = s.length;
    // left, right 分别记录 左括号  和  右括号 出现的数量
    let maxValidLength = 0, left = 0, right = 0;
    for (let i = 0; i < n; i++) {
        const char = s.charAt(i);
        if (char === '(') {
            left++;
        } else {
            right++;
        }
        // 如果 left===right，表示当前有匹配的()
        // 如果 right > left，表示已没有匹配项，将二者重置为0，以便重新寻找下一个匹配项
        // 如果 left > right，表示当前还没匹配完，需要继续匹配，但是无法记录 left一直大于right时的 maxValidLength；此时需要正序遍历完之后，再倒叙遍历匹配
        // 所以 maxValidLength 可以使用 计数器 * 2 来得到其值
        if (left === right) {
            maxValidLength = Math.max(maxValidLength, 2 * left);
        } else if (right > left) {
            left = right = 0;
        }
    }

    // 倒叙遍历前，注意计数器要清零
    left = right = 0;

    for (let i = n - 1; i >= 0; i--) {
        const char = s.charAt(i);
        if (char === '(') {
            left++;
        } else {
            right++;
        }
        if (left === right) {
            maxValidLength = Math.max(maxValidLength, 2 * left);
        } else if (left > right) {
            left = right = 0; 
        }
    }

    return maxValidLength;
};

时间复杂度：O(n)，如果匹配一次的时间为 t，其实用时为 2nt，而前面两种方法时间为 nt
空间复杂度：O(1)