来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1： 输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()" 示例 2： 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()" 示例 3： 输入：s = "" 输出：0 提示： 0 <= s.length <= 3 * 104 s[i] 为 '(' 或 ')'
解题思路
本题有三种解法，分别是动态规划法，栈法和两次遍历法。
动态规划法比较难想，我们使用一个dp数组来记录有效括号的长度，对于“（”来说，可以形成的有效括号总为0，因为需要有右括号才能形成有效括号。对于“）”来说，需要考虑三个部分，首先是对于第i个位置的右括号，需要判断第i - dp[i - 1] - 1的位置是否为左括号，如果不是左括号，那么就无法构成有效括号，dp[i] = 0，如果是，则有效括号长度可以+2，这个时候考虑第i个括号内部的长度，所以dp[i] += dp[i - 1],最后，我们还得考虑第i个括号对应的左括号前面有效括号的长度，所以dp[i] += dp[i - dp[i - 1] - 1],所以，递推公式为dp[i] = dp[i - dp[i - 1] - 1] + dp[i - 1] + 2(假设三个部分都为有效括号）
栈法和括号匹配的栈方法规则不太一样，提前将栈加入-1，方便边界处理，对于"("来说，入栈就可以了，对于")"来说，如果栈顶元素是-1或者是")"那么这个右括号是无效的括号直接入栈，如果栈顶元素是"("那么直接将栈顶出栈，这个右括号对应的最长有效括号长度就为这个右括号的下标减去了现在的栈顶元素。
双向遍历法其实才是刚刚开始想到的一个，只不过刚刚开始只想到了单向遍历，可以使用left 和right同时记录左右括号的个数，如果left = right 说明是有效括号，将其长度与最长长度比较并记录，如果left < right说明当前括号非法，将left与right全部置0，但是有个问题是这种方法容易漏掉"(()"这种情况，在这种情况下，left和right永远不能相等，这个时候可以从右往左再来一次遍历，操作方法和之前遍历类似，那么从右往左的遍历将漏掉"())"的情况，将两种遍历结合起来，就可以覆盖所有情况了。
代码展示
动态规划法：
class Solution { public: int longestValidParentheses(string s) { vector<int> dp(s.size(), 0); if(s.size() == 0) return 0; int Max = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') { dp[i] = 0; } else { if (i - 1 >= 0) { if(s[i - 1] == '(') { dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2; } else { if(i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') dp[i] = (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0 ) + dp[i - 1] + 2; else dp[i] = 0; } } } } for (auto iter : dp) Max = max(Max, iter); return Max; } };
栈法：
class Solution { public: int longestValidParentheses(string s) { stack<int> siStack; int iMax = 0; siStack.push(-1); for(int i = 0; i < s.size(); i++) { if(s[i] == '(') { siStack.push(i); } else { int top = siStack.top(); if(top == -1 || s[top] == ')') siStack.push(i); else { siStack.pop(); int iCount = i - siStack.top(); if(iCount > iMax) iMax = iCount; } } } return iMax; } };
两次遍历法：
class Solution { public: int longestValidParentheses(string s) { int iMax = 0; int left = 0, right = 0; for(int i = 0; i < s.size(); i++) { if(s[i] == '(') left++; else { right++; if(left < right) { left = 0; right = 0; } else if(left == right) { if(2* right > iMax) iMax = 2* right; } } } left = right = 0; for(int i = s.size() - 1; i >= 0; i--) { if(s[i] == ')') right++; else { left++; if(left > right) { left = 0; right = 0; } else if(left == right) { if(2* left > iMax) iMax = 2* left; } } } return iMax; } };
运行结果
