给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 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 stack = new linkedList<>();
stack.push(-1);
for(int i = 0 ; i < length;i++){
char c = s.charAt(i);
if(c == '('){
stack.push(i);
}else{ // ) 进行匹配 栈中全部都是(
stack.pop();
//需要考虑的是，当一开始碰到)时，栈本来就为空 这时候pop就会报错 所以可以先给栈中放一个默认值
if(stack.isEmpty()){
stack.push(i); //把最后一个不匹配的右括号的下标放入
}
max = Math.max(max,i - stack.peek());
}
}
return max;
}
解答成功:
执行耗时:2 ms,击败了55.10% 的Java用户
内存消耗:41.1 MB,击败了10.86% 的Java用户
思路3：不需要额外空间
使用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;
}
