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.1 public static int LogestValidParentheses(string s) 2 { 3 if (s.Length <= 1) 4 return 0; 5 6 Stack stack = new Stack (); 7 8 int start = s.Length; 9 int curr_length = 0;10 int max_length = 0;11 12 for(int i = 0; i < s.Length; i++)13 {14 if (s[i] == '(')15 stack.Push(i);16 17 if (s[i] == ')')18 {19 //if invalid parentheses in the middle set start back to s.Length20 if (stack.Count == 0)21 {22 start = s.Length;23 }24 else25 {26 start = Math.Min(start, stack.Pop());27 if (stack.Count == 0)28 {29 curr_length = i - start + 1;30 max_length = Math.Max(curr_length, max_length);31 }32 else33 {34 //if some left parentheses indices in the stack35 curr_length = i - stack.Peek();36 max_length = Math.Max(curr_length, max_length);37 }38 }39 }40 }41 42 return max_length;43 } 代码分析：
O(n)的解法。用Stack 存放左括号的index，碰到右括号，Pop出一个左括号的index，根据情况计算最长合理括号长度（如果stack.count == 0，从start开始算，如果stack还有东西，从最近一个左括号开始算）。
例如 "())(())("
| ( | ) | ) | ( | ( | ) | ) | ( | |
| Stack | [0) | [) | [) | [3) | [3,4) | [3) | [) | [) |
| start | 8 | 0 | 8 | 8 | 8 | 4 | 3 | 3 |
| curr_legnth | 0 | 2 | 0 | 0 | 0 | 2 | 4 | 4 |
| max_length | 0 | 2 | 2 | 2 | 2 | 2 | 4 | 4 |
"()((()()"
| ( | ) | ( | ( | ( | ) | ( | ) | |
| Stack | [0) | [) | [2) | [2,3) | [2,3,4) | [2,3) | [2,3,6) | [2,3) |
| start | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| curr_length | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 4 |
| max_length | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 4 |