题目的主要信息：

• 一个长度为$nn$的仅包含左右括号的字符串
• 计算最长的格式正确的括号子串的长度

方法一：栈

具体做法：

可以使用栈来记录左括号下标，每次遇到右括号则弹出左括号的下标，然后长度则更新为当前下标与栈顶下标的距离。因为遇到不符合的括号，可能会会使栈为空，因此需要使用start记录上一次结束的位置，这样用当前下标减去start即可获取长度。

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        int start = -1; //记录上一次连续括号结束的位置
        stack<int> st;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '(') //左括号入栈
                st.push(i);
            else{ //右括号
                if(st.empty()) //如果右括号时栈为空，不合法，设置为结束位置
                    start = i;
                else{
                    st.pop(); //弹出左括号
                    if(!st.empty()) //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                        res = max(res, i - st.top());
                    else //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                        res = max(res, i - start);
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历整个字符串
• 空间复杂度：$O(n)O(n)$，最坏全是左括号，栈的大小为$nn$

方法二：动态规划

具体做法：

可以用动态规划的方式，$dp[i]dp[i]$表示以下标为i的字符为结束点的最长合法括号长度，很明显知道左括号不能做结尾，因此但是左括号都是$dp[i]=0dp[i]=0$，我们遍历字符串，因为第一位不管是左括号还是右括号dp数组都是0，因此跳过，后续只查看右括号的情况，右括号有两种情况：

• 情况一：

  如图所示，左括号隔壁是右括号，那么合法括号需要增加2，可能是这一对括号之前的基础上加，也可能这一对就是起点，因此转移公式为：$dp[i]=(i>=2?dp[i-2]:0)+2dp[i]\; =\; (i\; >=\; 2\; ?\; dp[i\; -\; 2]\; :\; 0)\; +\; 2$

• 情况二：

  如图所示，与该右括号匹配的左括号不在自己旁边，而是它前一个合法序列之前，因此通过下标减去它前一个的合法序列长度即可得到最前面匹配的左括号，因此转移公式为：$dp[i]=(i-dp[i-1]>1?dp[i-dp[i-1]-2]:0)+dp[i-1]+2dp[i]\; =\; (i\; -\; dp[i\; -\; 1]\; >\; 1\; ?\; dp[i\; -\; dp[i\; -\; 1]\; -\; 2]\; :\; 0)\; +\; dp[i\; -\; 1]\; +\; 2$

每次检查完维护最大值即可。

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        if(s.length() == 0) //长度为0的串，返回0
            return res;
        vector<int> dp(s.length(), 0); //dp[i]表示以下标为i的字符为结束点的最长合法括号长度
        for(int i = 1; i < s.length(); i++){ //第一位不管是左括号还是右括号都是0，因此不用管
            if(s[i] == ')'){ //取到左括号记为0，有右括号才合法
                if(s[i - 1] == '(') //如果该右括号前一位就是左括号
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; //计数+2
                else if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') //找到这一段连续合法括号序列前第一个左括号做匹配
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            res = max(res, dp[i]); //维护最大值
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一次字符串
• 空间复杂度：$O(n)O(n)$，动态规划辅助数组的长度为$nn$