题目介绍
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
使用栈解决
这题让求的是最长有效括号长度，一个有效的括号一定是满足下面两个条件：
-
左括号和右括号的数量一定是相等的。
-
在有效括号的任何位置左括号的数量一定是大于等于右括号的数量。
根据这两个特性我们可以使用栈来解决，栈中存放的是字符的下标，解决思路就是：
-
如果遇到左括号我们就把他的下标压栈。
-
如果遇到右括号，栈顶元素出栈，如果栈不为空说明出栈的元素和这个右括号匹配，我们需要计算他们的长度，保留最大值即可。如果栈为空，直接把这个右括号所在的下标压栈。
这里要注意如果给定的字符串从一开始就是有效的括号，比如"()())"前4个符号是有效的括号，我们是没法计算他的长度的，因为第一个字符前面是没有字符的，所以我们默认第一个字符前面的下标是-1，然后把他压栈，我们以示例2为例画个图来看下。
最后看下代码：
class Solution {
public:
int flags[20000];
int longestValidParentheses(string s) {
int n = s.size();
stack<int> stk;//存储的是下标
for(int i = 0; i < n; ++i){
if(s[i] == '(')
stk.push(i);//左括号push
else{
if(stk.empty())
flags[i] = 1;
else
stk.pop();
}
}
while(!stk.empty()){
flags[stk.top()] = 1;
stk.pop();
}
int res = 0, len = 0;
for(int i = 0; i < n; ++i){
if(flags[i] == 0)
++len;
else{
res = max(res, len);//长度更新
len = 0;
}
}
return max(res, len);//可能需要考虑最后的位
}
};
动态规划
再来看下动态规划该怎么解决，我们用dp[i]表示以是s[i]为结尾的最长有效括号长度，如果要计算dp[i]就会有下面几种情况：
-
第i个字符是左括号"("，那么以他结尾的是构不成有效括号的，所以dp[i]=0;
-
第i个字符是右括号")"，那么以他结尾的是有可能构成有效括号的，所以还需要继续判断：
-
这里我们需要判断他前面的也就是第i-1个字符，如果第i-1个字符是左括号"("，类似于……()，那么最长有效括号就是第i-2个字符之前构成的最长有效括号+2，也就是dp[i]=dp[i-2]+2。
-
如果第i-1个字符也是右括号")"，类似于……((……))，如下图所示，我们还需要判断第i -1- dp[i - 1]个字符是否是左括号"(",如果是"("，那么递推公式是dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]，这里dp[i - dp[i - 1] - 2]是第一个省略号构成的有效括号长度，这个不要忘了。
最后看下代码：
class Solution {
public:
int dp[20000];
int longestValidParentheses(string s) {
int n = s.size();
for(int i = 1; i < n; ++i){
if(s[i] == ')'){//合法的子串一定以右括号结尾
if(s[i-1] == '(')
dp[i+1] = dp[i-1] + 2;
else if(i-1-dp[i] >= 0 && s[i-1-dp[i]] == '(')
dp[i+1] = dp[i] + dp[i-1-dp[i]] + 2;
}
}
return *max_element(dp+1, dp+n+1);
}
};
