题干
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入
: "(()"
输出
: 2
解释
: 最长有效括号子串为
"()"
示例 2:
输入
: ")()())"
输出
: 4
解释
: 最长有效括号子串为
"()()"
想法
栈，栈底存尚未匹配的最后一个）的位置
遍历数组 （的话直接放入栈
）的话，栈顶出去 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
java代码
package daily
;
import java
.util
.Stack
;
public class LongestValidParentheses {
public int longestValidParentheses(String s
) {
int maxres
=0;
Stack
<Integer> stack
=new Stack<>();
stack
.push(-1);
for (int i
=0;i
<s
.length();i
++){
if(s
.charAt(i
)=='('){
stack
.push(i
);
}
else {
stack
.pop();
if(stack
.isEmpty()){
stack
.push(i
);
}
else {
maxres
=Math
.max(maxres
,i
-stack
.peek());
}
}
}
return maxres
;
}
public static void main(String
[] args
){
String s
=")()())";
LongestValidParentheses longestValidParentheses
=new LongestValidParentheses();
System
.out
.println(longestValidParentheses
.longestValidParentheses(s
));
}
}
我的leetcode代码都已经上传到我的githttps://github.com/ragezor/leetcode
