给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

1.答案方法一：动态规划。

class Solution {public int longestValidParentheses(String s) {int maxans = 0;int[] dp = new int[s.length()];for (int i = 1; i < s.length(); i++) {if (s.charAt(i) == ')') {if (s.charAt(i - 1) == '(') {//组成了"()"dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;//加2} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {//组成了"))"dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;}maxans = Math.max(maxans, dp[i]);//找最大值}}return maxans;}
}

2.答案方法二：利用辅助空间栈。

class Solution {public int longestValidParentheses(String s) {int maxans = 0;Deque<Integer> stack = new LinkedList<Integer>();stack.push(-1);//预先存入一个-1for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {//遇到左括号stack.push(i);//将左括号的下标存入} else {//遇到右括号stack.pop();//取出一个元素if (stack.isEmpty()) {//如果取出后，栈为空，说明没有左括号stack.push(i);//将这个右括号的下标压入栈，作为最后一个没有被匹配的右括号的下标} else {//栈不为空，说明存在左括号，并且被取出来匹配了当前的右括号maxans = Math.max(maxans, i - stack.peek());//更新最大长度}}}return maxans;}
}

3.自己解题的时候是从后往前进行遍历，然后根据右括号出现的次数来判断此时长度，但是这种方法还是遇到了问题，有些情况没有考虑进去。自己的思想是和答案方法三比较相似的。

   答案方法三：此时不需要额外的辅助空间，使用两个指针。

 

class Solution {public int longestValidParentheses(String s) {int left = 0, right = 0, maxlength = 0;//从前往后遍历for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {//遇到左括号left++;//left+1} else {//遇到右括号right++;//right+1}if (left == right) {//说明匹配成功maxlength = Math.max(maxlength, 2 * right);} else if (right > left) {//右括号数量大于左括号，说明断开了，没有左括号可以匹配这个多的右括号left = right = 0;}}left = right = 0;//利用从后往前遍历来计算那些从前往后遍历不能得到结果的情况。for (int i = s.length() - 1; i >= 0; i--) {if (s.charAt(i) == '(') {left++;} else {right++;}if (left == right) {maxlength = Math.max(maxlength, 2 * left);} else if (left > right) {//左括号数量大于右括号，说明断开了，没有右括号可以匹配这个多的左括号left = right = 0;}}return maxlength;}
}

题源：力扣