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.
思路：括号匹配使用栈stack来模拟匹配的过程。使用栈来存储左括号的位置信息，失去匹配的右括号作为重新计数的分隔符。
class Solution { public: int longestValidParentheses(string s) { stack<int> st; int n=s.size(); if(n==0) return 0; int last=-1; int longest=0; for(int i=0;i<n;i++) { if(s[i]==‘(‘) { st.push(i); } else { if(st.empty()) last=i; else { st.pop(); if(st.empty()) longest=max(longest,i-last); else longest=max(longest,i-st.top()); } } } return longest; } };
Longest Valid Parentheses,布布扣,bubuko.com
原文：http://www.cnblogs.com/awy-blog/p/3815135.html