32. [✔][H]最长有效括号

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

---

题解：

逻辑梳理：

以s = ")()())"为例，stack=[],dp=[].

i=0时，")"字符，dp[1]=0, dp = [empty,0,empty,empty,empty,empty,empty]

i=1时，"("字符，dp[2]=0,dp = [empty,0,0,empty,empty,empty,empty],stack=[1]

i=2时，")"字符，leftIndex=1, stack=[], len=2-1+dp[1]+1=2, dp[3]=2,dp = [empty,0,0,2,empty,empty,empty]

i=3时，"("字符，dp[4]=0,dp = [empty,0,0,2,0,empty,empty],stack=[3]

i=4时，")"字符，leftIndex=3, stack=[], len=4-3+dp[3]+1=4, dp[5]=4,dp = [empty,0,0,2,0,4,empty]

i=5时，")"字符，dp[6]=0,dp = [empty,0,0,2,0,4,0]

以上可以看出，stack存储的是未匹配的做括号的索引，当遇到右括号时会pop出去。

dp[i]存储的是以 s[i-1] 结尾的最长合法括号子串长度，所以dp[0]=empty。

i - leftindex + dp[leftindex] + 1;这个计算公式表示（i-leftindex+1）为当前合法字符串长度，再加上之前dp[leftindex]也就是s[0,leftindex-1]中合法字符串长度的和

/*
 * @lc app=leetcode.cn id=32 lang=typescript
 *
 * [32] 最长有效括号
 */

// @lc code=start
function longestValidParentheses(s: string): number {
    let stack: number[] = [];//stack只是记录最近的(括号的索引值
    // dp[i] 的定义：记录以 s[i-1] 结尾的最长合法括号子串长度
    let dp: number[] = [];// 每次都会记录一个dp[i],无论是0还是一个具体其他数字


    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        // 左括号
        if (char === "(") {
            stack.push(i);
            dp[i + 1] = 0;
        } else { //右括号
            if (stack.length > 0) {
                // 配对的左括号对应索引
                let leftindex = stack.pop()!;
                // 以这个右括号结尾的最长子串长度
                let len = i - leftindex + dp[leftindex] + 1;
                dp[i + 1] = len;
            } else {
                // 孤零零一个右括号
                dp[i + 1] = 0;
            }
        }
    }


    let res = 0;
    for (let i = 0; i < dp.length; i++) {
        res = Math.max(dp[i], res);
    }
    return res;
};
// @lc code=end