[LeetCode] Longest Valid Parentheses, Solution

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.

» Solve this problem

[Thoughts]
维护一个栈，每次维护上一个可能的左边际。


[Code]

1:       int longestValidParentheses(string s) {  
2:            const char* str = s.c_str();  
3:            int nMax=0;  
4:            const char *p = str;  
5:            vector<const char*> sta;  
6:            while(*p !='\0')  
7:            {  
8:                 if(*p == '(')  
9:                 {  
10:                      sta.push_back(p);                      
11:                 }  
12:                 else  
13:                 {  
14:                      if(!sta.empty() && *sta.back()=='(')  
15:                      {  
16:                           sta.pop_back();  
17:                           nMax = max(nMax, p-(sta.empty()?str-1:sta.back()));  
18:                      }  
19:                      else  
20:                      {  
21:                           sta.push_back(p);  
22:                      }  
23:                 }  
24:                 p++;  
25:            }  
26:            return nMax;  
27:       }