最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：
输入：s = “”
输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
解法一：栈的用法
一般来说解决括号的匹配方法都是使用栈来进行匹配，所以第一时间就可以想到这种方法。栈的优势在于能够把左括号压入栈中然后遇到右括号在弹出进行匹配，完美符合括号匹配的法则。
这道题的目的在于找到最长有效括号字串，先来找最长有效括号字串的特点，那就是：
1，一定是右括号结尾。
2，一定是连续在一起结算括号
这其实就是有效括号的特点，所以我们一般这样解决问题：将左括号’(‘的信息压入栈中，在遍历中找到右括号’)’,纵看整个字符串，不难发现字符串总是被一些无法正常匹配的符号给截断成不同的有效字串，所以我们可以把这些无法正常匹配的符号的位置信息存放在栈中，然后正常的字串匹配完毕可以将当前的位置信息减去栈顶元素的位置，也就是截断字符串的非正常括号，这样就能一个个计算字串的长度，最终比较得出最大值。
其中无法正常匹配的符号也分两种情况：
1.左括号’(‘：直接正常流程压入栈中，记录位置信息。
2.右括号’)’：先pop()，无法匹配说明栈中已经没有位置信息，那么也直接把’)’的位置信息压入栈中
有两种解题方法：
1.直接计算长度
先将-1压入栈中，这样即使刚开始就出现可以结算的”()”或者不可结算的单个”)”也能计算，比如说”()”，那就是先把’(‘压进栈中，然后遇到’)’后弹出，将’)’的位置信息减去栈顶元素top()，这样可以得出长度。
这样依次计算找出最大值。
2.先找出无法匹配的括号，标记出来
创建情况数组bool d[],遍历一遍字符串，遇到异常情况的话把异常情况标记出来，数组标为1。
之后寻找数组连续0最多是多长。
动态规划法
思路和算法
我们定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0 。显然有效的子串一定以 ‘)’ 结尾，因此我们可以知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’ 在 dp 数组中对应位置的值。
我们从前往后遍历字符串求解 dp 值，我们每两个字符检查一次：
s[i]=‘)’ 且 s[i−1]=‘(’，也就是字符串形如 “……()”，我们可以推出：
dp[i]=dp[i−2]+2
我们可以进行这样的转移，是因为结束部分的 “()” 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2 。
s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”，我们可以推出：
如果 s[i−dp[i−1]−1]=‘(’，那么
dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2
我们考虑如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 sub‘s），对于最后一个 ‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 sub’s的前面）。因此，如果子字符串 sub‘s的前面恰好是 ‘(’ ，那么我们就用 2 加上 sub’s的长度（dp[i−1]）去更新 dp[i]。同时，我们也会把有效子串 “(sub‘s)” 之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]。
最后的答案即为 dp 数组中的最大值。
复杂度分析
时间空间复杂度都是O(n)
