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 class Solution { 2 public: 3 int longestValidParentheses(string s) { 4 stack<int> stk; 5 int ret = 0; 6 7 if (s.size() <= 1) return 0; 8 9 stk.push(0); 10 11 for (int i = 1; i < s.size(); i++){ 12 if (!stk.empty() && s[stk.top()] == ‘(‘ && s[i] == ‘)‘){ 13 stk.pop(); 14 }else{ 15 stk.push(i); 16 } 17 } 18 19 if (stk.empty()){ 20 return s.size(); 21 }else if (stk.top() != s.size() - 1){ 22 stk.push(s.size()); 23 } 24 25 while (!stk.empty()){ 26 int tmp = stk.top(); 27 stk.pop(); 28 if (stk.empty()) { 29 ret = max(ret, tmp); 30 }else{ 31 ret = max(ret, tmp - stk.top() - 1); 32 } 33 } 34 35 return ret; 36 } 37 };
[LeetCode] 32. Longest Valid Parentheses
原文：http://www.cnblogs.com/amadis/p/6707946.html