1.使用栈解决
重点：记录不能成对的括号,之后再进行相减。
时间复杂度O(n)
class Solution {
public int longestValidParentheses(String s) {
char[] ch=s.toCharArray();
Stack<Integer> stack=new Stack<Integer>();
for(int i=0;i<s.length();i++){
if(ch[i]=='('){
stack.push(i);
}else {
if (stack.size() != 0) {
if (ch[stack.peek()] == '(') {
stack.pop();
} else {
stack.push(i);
}
} else {
stack.push(i);
}
}
}
if(stack.size()==0){
return s.length();
}else{
int end=s.length();
int max=-1;
while(stack.size()!=0){
int top=stack.peek();
stack.pop();
max=max>(end-top-1)?max:(end-top-1);
end=top;
}
max=max>(end-0)?max:(end-0);
return max;
}
}
}
2.使用dp
时间复杂度O(N);
重点是注意是否有嵌套的括号或者顺序不嵌套的括号。
public class Solution {
public static int longestValidParentheses(String s) {
char[] ch=s.toCharArray();
int[] dp=new int[s.length()];
int count=0;
int max=0;
for(int i=0;i<s.length();i++){
if(ch[i]=='('){
count++;
}else{
if(count>0){
dp[i]=dp[i-1]+2;
dp[i]+=(i-dp[i])>0?dp[i-dp[i]]:0;
max=Math.max(max,dp[i]);
count--;
}
}
}
return max;
}
}
