[力扣_32] 最长有效括号
题目入口：点击进入
相关算法：
- 动态规划——时间复杂度O(n)，空间复杂度O(n)
- 栈——时间复杂度O(n)，空间复杂度O(n)
- 两边扫描——时间复杂度O(n)，空间复杂度O(1)
思路与算法：
(这道题的官方题解通俗易懂)
我们来抓这道题的两个关键字，括号和子串，看到这两个词，我们很容易就能想到栈和滑动窗口，我们知道，括号都是成对出现的，所以最长合理子串长度肯定是一个偶数，我们从最接近字符串长度的偶数长度开始截取子串，逐次去验证看是否合理，验证的时候使用栈，一旦遇到合理的子串，直接返回即可，如下图所示：
但这样一定会超时，从上述我们可以想到以下几种优化方法
动态规划
这道题其实很难想到动态规划(可能是我菜吧)，但是其动态转移方程却很好理解，思路如下所示，我们用一个一维的dp数组来记录：以当前坐标为结尾的有效括号长度字符串的长度是多少这个状态
**动态规划的题目一般分成三步：
1、确定状态，也就是你的答案表是存什么答案的。
2、确定状态转移方程，也就是怎么将你的答案表填满，换句话说，就是一些表达式。
3、确定边界情况，什么情况下有可能越界，要单独判断考虑（有可能无边界情况）。**
关键是，怎么找到当前坐标的状态dp[i]跟i之前坐标的状态的依赖关系：
- 如果当前坐标 i 是一个左括号 '(' ，很明显有效字符串不会以左括号为结尾，所以这个状态是0
如果当前坐标 i 是一个右括号 ‘ )’那么：
- 如果它前一个 i - 1 是'('，它们可以组成一对儿，那么dp[i]至少是2
如果它前一个 i - 1 是')'，虽然它们不能成对儿，但是，')'说明它可能是某个有效字符串的结尾，那我们就得检查这个坐标 i - 1 的状态了
- 如果dp[i-1]是0，那就没戏了，dp[i]也只能是0了
- 如果dp[i-1]>0，那么，i 的前面有一段有效括号的字符串，那只要判断这段字符串前面的字符是不是 ( 就好了，如果是，dp[i] = dp[i-1]+2，如果不是，dp[i] = 0
这个时候，里面看完了，但是还没结束，如果到了这里，dp[i]大于0的话，还有一种情况：
- 需要探寻dp[i-dp[i-1]-2]也就是其外部的一个长度。
从上我们可以推导出状态转移方程：
- dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2，其中dp[i-1]为其内部可能的字符串长度，dp[i-dp[i-1]-2]是其外部可能的字符串长度
- 在探寻外部的时候，需要注意边界问题。
代码如下所示：
int longestValidParentheses(char * s){
int max=0;
int sleng=strlen(s);
if(!sleng) return NULL;
int dp[sleng];
memset(dp,0,sizeof(int)*sleng);
for(int i=0;i<sleng;i++)
{
if(s[i]==')')
{
if(i>0&&s[i-1]=='(')
{
if(i-2 >= 0) dp[i]=2+dp[i-2];
else dp[i]=2;
}
else
{
if(i>0&&i-dp[i-1]-1>=0&&s[i-dp[i-1]-1]=='(')
{
if(i-dp[i-1]-2>=0) dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2];
else dp[i]=2+dp[i-1];
}
}
if(dp[i]>max)
max=dp[i];
}
}
return max;
}栈
撇开动态规划的方法，其实这道题最容易的还是想到用Stack来做，毕竟在我们刚刚接触栈这种数据结构的时候，就有有效括号匹配的问题
通过栈，我们可以在遍历给定字符串的过程中去判断到目前位置扫描的子串的有效性，同时能得到最长有效括号的长度
具体做法是我们始终保持栈底元素为当前已经遍历过的元素中【最后一个没有被匹配的右括号的下标】，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标
- 对于遇到的每个"("，我们将它的下标放入栈中
对于遇到的每个")"，我们先弹出栈顶元素表示匹配了当前右括号
- 如果栈为空，说明当前的右括号为没有匹配的右括号，我们将其下标放入栈中来更新我们之前提到的【最后一个没有匹配的右括号的下标】
- 如果栈不为空，当前右括号的下标减去栈顶元素即为【以该右括号为结尾的最长有效括号长度】
我们从前往后遍历字符串并更新答案即可。
需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提到的【最后一个没有被匹配的右括号的下标】，为了保持统一，我们在一开始的时候往栈中放入一个值为-1的元素
图示如下：
代码如下所示：
int longestValidParentheses(char * s){
int sleng=strlen(s);
int maxlen=0;
int top=-1;
int *Stack=(int*)malloc(sizeof(int)*(sleng+1));
Stack[++top]=-1;
for(int i=0;i<sleng;i++){
if(s[i]=='('){
top++;
Stack[top]=i;
}
else if(s[i]==')'){
top--;
if(top== -1 )//Stack Null
{
top++;
Stack[top]=i;
}
else{
maxlen=maxlen<(i-Stack[top])?(i-Stack[top]):maxlen;
}
}
}
return maxlen;
}奇技淫巧（两边扫描）
在此方法中，我们利用两个计数器 left 和 right ，首先，我们从左到右遍历字符串，对于遇到的每个"("，我们增加left计数器，对于遇到的每个")"，我们增加right计数器，每当left和right计数器相等时，最长有效括号即为它们其中一个的二倍。
当right(右括号)比left(左括号)大的时候，我们将left和right计数器同时变回0
这样的做法贪心的考虑了当前字符下标结尾的有效括号长度，每次当右括号数量多余左括号数量的时候，之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算
但按上述会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即使(()，这种时候最长有效括号是求不出的。
解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反过来了：
- 当left计数器比right计数器大时，我们将left和right计数器同时变为0
- 当left计数器和right计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。
这样我们就能覆盖所有情况从而求解出答案。
代码如下所示：
int longestValidParentheses(char * s){
int sleng=strlen(s);
int left=0;//左括号匹配
int right=0; //右括号匹配
int maxlen=0;
int flag=0;
while(1){
if(flag==2) break;
//正序
if(flag == 0){
for(int i=0;i<sleng;i++){
if(s[i]=='(') left++;
else if(s[i]==')') right++;
if(left==right) maxlen=maxlen > (left*2) ? maxlen : (left*2);
if(right>left)left=right=0;
}
flag++;
left=right=0;
}
else{
for(int i=sleng-1;i >= 0;i--){
if(s[i]=='(') left++;
else if(s[i]==')') right++;
if(left==right) maxlen=maxlen > (left*2) ? maxlen : (left*2);
if(left > right) left=right=0;
}
flag++;
}
}
return maxlen;
}