1.使用棧解決
重點(diǎn)：記錄不能成對(duì)的括號(hào),之后再進(jìn)行相減。
? ? 時(shí)間復(fù)雜度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
? ? 時(shí)間復(fù)雜度O(N);
? ? 重點(diǎn)是注意是否有嵌套的括號(hào)或者順序不嵌套的括號(hào)。
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;
? ? }
}
