32. 最长有效括号 给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”
分析： 先来想最直接的解法。 1.dp[i]：以s[i]作为结尾的序列中最长有效括号子串长度。 2.借助栈： i）当前是左括号，和它匹配的右括号一定在后面，所以它无法扩展有效括号长度，"（"入栈，左括号作为结尾的dp[i]=dp[i-1]， ii)“）”看栈中是否有和它匹配的左括号，如果有，那长度就在之前的基础上+2,如果没有dp[i]=dp[i-1]. 但是会有几种特殊情况： 对于无法扩展有效括号的那些位置，我们直接让它等于前一个位置的有效括号长度即可（dp[i]=dp[i-1]）。 但是当前右括号如果可以和之前一个多余左括号匹配的话，情况就比较复杂了。我们需要注意这个栈的一个性质： 栈顶左括号的含义：最近一个没有匹配的左括号，也就是说假设栈顶(的位置为p，当前)为q，则p和q之间只可能是有效括号串，而不可能有多余的左右括号。 （因为栈顶代表的是最近一个没有匹配的左括号，所以这之间的左括号一定都是被匹配了的，而如果之间还有没匹配的右括号那就不可能轮到当前右括号来匹配。） 为了找到最近一个没有匹配的左括号或者右括号的位置，用栈来记录最近一个未匹配左括号的下标，用一个变量来记录最近未匹配的右括号下标。 j = 最新找到匹配右括号的栈顶左括号 i = 最新找到匹配左括号的右括号（当前遍历位置） 1.对于左右括号阻断的情况，我们应该重新计算有效长度： dp[i] = i-j+1 2.对于左右括号阻断的情况: dp[i] = dp[j-1]+i-j+1
class Solution { public: int longestValidParentheses(string s) { if(s.size()==0)return 0; vector<int>dp(s.size(),0); stack<int>st; dp[0] = 0; if(s[0]=='(') st.push(0); int ind,res=0; for(int i=1;i<s.size();i++){ if(s[i]==')'){ //s[i]=')'，看栈里是否有多余的左括号和它匹配 //假设栈顶(的含义：最近一个没有匹配的( //假设栈顶(的位置为p，当前)为q，则p和q之间只可能是有效括号串，而不可能有多余的右括号 if(st.empty()){ dp[i] = dp[i-1]; ind = i;//记录多余右括号下标 } else{ int j = st.top(); st.pop(); if((!st.empty()&&st.top()==j-1)||ind==j-1||j==0) dp[i] = i-j+1; else{ dp[i]=dp[j-1]+i-j+1; } } }else{ //s[i]='('说明这个'('一定是多出来的，不可能进一步构成最长有效括号 //则有效括号长度等于前一个位置的长度，括号入栈 st.push(i); dp[i]=dp[i-1]; } res = max(res,dp[i]); } return res; } };