给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"输出：2解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"输出：4解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""输出：0
提示：
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
Related Topics
栈
字符串
动态规划
思路1：动态规划参考leetcode理解：通过分析，有效的括号有2种形式
第一种：()()、()(()，没有嵌套的括号格式，当s[i] = ')' && s[i-1] == '('，那么dp[i] = dp[i-2] + 2。
第二种：123(())，是这种嵌套的形式，当s[i] = ')' && s[i-1] == ')'时，我们需要匹配s[i]和s[i-dp[i-1]-1],i-dp[i]-1刚好是3后面第一个括号的位置，如果匹配成功，那么dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2。
这里的dp[i-1] 计算的是嵌套里面的长度。
dp[i- dp[i-1] - 2] 计算的嵌套外面的长度，也就是前面123这个地方的长度。i减去嵌套内部的长度和自身匹配的2个长度就是3这个位置。
public int longestValidParentheses(String s) { int length = s.length(); int max = 0; int[] dp = new int[length]; for(int i = 1; i < length;i++){ if(s.charAt(i)==')'){ if(s.charAt(i-1) == '('){ //dp[i] = dp[i-2] + 2 但是必须要保证i >=2 dp[i] = (i >=2 ? dp[i-2] : 0) + 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; } if(max < dp[i]){ max = dp[i]; } } } return max;}解答成功: 执行耗时:1 ms,击败了100.00% 的Java用户 内存消耗:41.4 MB,击败了5.08% 的Java用户
思路2 ： 栈在栈中存放括号的下标，通过下标计算长度。主要思想：及时更新最后一个不匹配右括号的下标放入栈中。那么当栈初始时，栈中并没有不匹配的右括号，所以需要一个默认值。
遇到左括号直接放入栈中。
遇到右括号，出栈对右括号进行匹配。
如果此时栈为空，说明这是一个不匹配的右括号，需要把下标放入栈中。
不为空，计算长度，i-栈顶中的下标。
public int longestValidParentheses(String s) { int max = 0; int length = s.length(); Deque
使用2个计数器left和right，从左往右遍历字符串，对于左括号left加1，右括号right加1。
当left == right时，直接计算有效长度。
当left 当left>right继续匹配，这一种情况，从左往右却无法计算。例：(() 这时候，我们需要从右往左遍历， 当left==right时，直接计算长度。 当left< right时，继续匹配。刚好解决(()这种情况。 当left>right时，左括号大于右括号，说明此时已经无法匹配，需要重置left和right。 public int longestValidParentheses(String s) { int left = 0; int right = 0; int length = s.length(); int max = 0; for(int i = 0 ; i < length;i++){ char c = s.charAt(i); if(c == '('){ left++; }else{ right++; } if(left == right){ max = Math.max(left*2,max); }else if(left < right){ left = right = 0; } } left = right = 0; for(int i = length - 1; i >= 0 ; i--){ char c = s.charAt(i); if(c == '('){ left++; }else{ right++; } if(left == right){ max = Math.max(left*2,max); }else if(left > right){ left = right = 0; } } return max;}