LC.32. 最长有效括号

挺好的一个题，这里主要再分析一下官方的解法。

思路:

1. $dp$ 。

令以下标 $i$ 结尾的字符串的最大长度为 $dp[i]$ ，显然 $s[i]='('$ ， $dp[i]=0$ .

当 $s[i]=')'$ ，需要讨论两种情况。

$1:$ $s[i-1]='('$ ，这样显然有 $dp[i]=dp[i-2]+2$ .

$2:s[i-1]=')'$ ，因为我们已知 $dp[i-1]$ ，我们可以找到 $dp[i-1]$ 的开始匹配的前面一个位置即 $pos=(i-1)-dp[i-1]$ ，显然如果 $s[pos]=')'$ ，是不能更新的，因为 $s[pos]$ 一定是未被匹配的 $')'$ ，不然 $dp[i-1]$ 会包含掉它，所以显然 $s[pos]='('$ ，才能与 $s[i]=')'$ 进行匹配，然后再加上 $dp[pos-1]$ 的长度就可以了。

即 $dp[i]=dp[i-1]+2+dp[i-2-dp[i-1]]$

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

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.length(),ans=0;
        vector<int>dp(n,0);
        for(int i=1;i<n;i++){
            if(s[i]=='(') dp[i]=0;
            else if(s[i-1]=='('){
                 dp[i]=(i>=2?dp[i-2]:0)+2;
            }
            else if(i-dp[i-1]>0&&s[i-1-dp[i-1]]=='(')
                dp[i]=(i-2-dp[i-1]>=0?dp[i-2-dp[i-1]]:0)+2+dp[i-1];
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};

2.栈。

显然对于这样的后缀表达式问题，用栈是很方便的。这里是参考官方大大的解法，预先放一个元素 $-1$ ，保证栈底是未被匹配的最后一个右括号下标，如果是左括号直接入栈，否则弹出栈顶元素，如果栈是空的表示不能更新，否则长度为 $i-sk.top()$

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

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.length(),ans=0;
        stack<int>sk;sk.push(-1);
        for(int i=0;i<n;i++){
            if(s[i]=='(') sk.push(i);
            else {
                sk.pop();
                if(sk.empty()) sk.push(i);
                else ans=max(ans,i-sk.top());
            }
        }
        return ans;
    }
};

3.统计左右括号数。

这种方法我觉得比第二种好理解点，先顺序遍历一遍，如果是左括号 $l++$ ,否则 $r++$ ,左右括号数相等就更新长度，若 $r>l$ ，则可以舍弃掉前面所有的括号， $l=r=0$ 。

因为顺序遍历没有考虑到 $l始终>r$ 的情况，这样就更新不了。

所以再逆序遍历一遍， $l>r$ 时 $l=r=0$ .这样就考虑到所有情况了。

时间复杂度： $O(2n)$

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.length(),ans=0;
        int l=0,r=0;
        for(int i=0;i<n;i++){
            if(s[i]=='(') l++;
            else r++;
            if(l==r) ans=max(ans,l*2);
            else if(r>l) l=r=0;
        }
        l=r=0;
        for(int i=n-1;i>=0;i--){
            s[i]=='('?l++:r++;
            if(l==r) ans=max(ans,l*2);
            else if(l>r) l=r=0;
        }
        return ans;
    }
};