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.
本题是括号匹配问题，用栈存放‘（’，如果碰到‘）’就出栈。时间：17ms，代码如下：
class Solution { public: int longestValidParentheses(string s) { if (s.empty()) return 0; stack< pair<char,int> > validStack; for (string::const_iterator iter = s.begin(); iter != s.end(); iter++){ if (*iter == ‘(‘) validStack.push(make_pair(‘(‘,iter - s.begin())); else if (*iter == ‘)‘){ if (!validStack.empty() && validStack.top().first == ‘(‘){ validStack.pop(); } else validStack.push(make_pair(*iter,iter - s.begin())); } } if (validStack.empty()) return s.size(); int temp = validStack.top().second; int max = s.size() - 1 - temp ; validStack.pop(); while (!validStack.empty()){ if (max < temp - validStack.top().second - 1) max = temp - validStack.top().second - 1; temp = validStack.top().second; validStack.pop(); } if (max < temp) return temp; return max; } };
[LeetCode] #32 Longest Valid Parentheses
原文：http://www.cnblogs.com/Scorpio989/p/4576684.html