Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Version 1

仅仅考虑了()()这种情况，当input:()(())时输出为2，expected为:6

(())也是valid parentheses

1 public class Solution { 2     public int longestValidParentheses(String s) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         int max = 0; 6         int len = s.length(); 7         Stack
     
       stack = new Stack
      
       (); 8         int lastIndex = -1; 9         10         int curLen = 0;11         for(int i = 0; i < len; i++){12             if(!stack.empty()){13                 char top = stack.peek();14                 char c = s.charAt(i);15                 16                 if(match(top, c)){17                     if(i - lastIndex == 2){18                        curLen += 2; 19                        lastIndex = i;20                        if(curLen > max){21                             max = curLen;22                        }23                     } else {24                         curLen = 2;25                         if(curLen > max){26                             max = curLen;27                         }28                         lastIndex = i;29                     }30                     stack.pop();31                 } else {32                     stack.push(c);33                 }34             } else {35                 char c = s.charAt(i);36                 stack.push(c);37             }38         }39         40         return max;41     }42     43     boolean match(char a, char b){44         if(a == '(' && b == ')'){45             return true;46         } else {47             return false;48         }49     }50 }
      
     

Version 2：

通过维护一个左边界来计算Longest Valid Parentheses

 

1 class Node{ 2     char c; 3     int i; 4     public Node(char c, int i){ 5         this.c = c; 6         this.i = i; 7     } 8 } 9 10 public class Solution {11     public int longestValidParentheses(String s) {12         // Start typing your Java solution below13         // DO NOT write main() function14         int max = 0;15         int len = s.length();16         Stack
     
       stack = new Stack
      
       ();17         int lastIndex = -1;18         19         int curLen = 0;20         for(int i = 0; i < len; i++){21             if(!stack.empty()){22                 Node top = stack.peek();23                 char c = s.charAt(i);24                 25                 if(match(top.c, c)){26                     stack.pop();27                     if(stack.empty()){28                         max = Math.max(max, i- (-1));29                     } else{30                         max = Math.max(max, i - (stack.peek()).i);31                     }32                     33                 } else {34                     stack.push(new Node(c, i));35                 }36             } else {37                 char c = s.charAt(i);38                 stack.push(new Node(c, i));39             }40         }41         42         return max;43     }44     45     boolean match(char a, char b){46         if(a == '(' && b == ')'){47             return true;48         } else {49             return false;50         }51     }52     53 }
      
     

参考：

对代码进行重构，'('只会入栈，')'可能入栈，可能出栈

Version 3

1 class Node{ 2     char c; 3     int i; 4     public Node(char c, int i){ 5         this.c = c; 6         this.i = i; 7     } 8 } 9 10 public class Solution {11     public int longestValidParentheses(String s) {12         int max = 0;13         int len = s.length();14         Stack
     
       stack = new Stack
      
       ();15         stack.push(new Node(')', -1));        16         int curLen = 0;17         for(int i = 0; i < len; i++){18             char c = s.charAt(i);19             if(c == '('){20                 stack.push(new Node(c, i));21             } else {22                 Node top = stack.peek();23                 if(top.c == '('){24                     stack.pop();25                     max = Math.max(max, i - stack.peek().i);26                 } else {27                     stack.push(new Node(c, i));28                 }29             }30         }31         return max;32     }33 }