LC.32. 最长有效括号

传送门

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

思路:

1.$dp$。

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

当$s[i]{=}^{\prime }{)}^{\prime }$，需要讨论两种情况。

$1:$ $s[i-1]{=}^{\prime }{(}^{\prime }$ ，这样显然有$dp[i]=dp[i-2]+2$.

$2:s[i-1]{=}^{\prime }{)}^{\prime }$ ，因为我们已知$dp[i-1]$，我们可以找到$dp[i-1]$的开始匹配的前面 一个位置即$pos=(i-1)-dp[i-1]$，显然如果$s[pos]{=}^{\prime }{)}^{\prime }$，是不能更新的，因为$s[pos]$一定是未被匹配的${}^{\prime }{)}^{\prime }$，不然$dp[i-1]$会包含掉它，所以显然$s[pos]{=}^{\prime }{(}^{\prime }$，才能与$s[i]{=}^{\prime }{)}^{\prime }$进行匹配，然后再加上$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; } };