Longest Valid ParenthesesMar 1 '125700 / 20657
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.
之前大摩面试时，问到了这题，当时愚昧了。
一开始，写错了。
后来，想了个N^2的方法。 T_T。
不过好歹这次一次AC :)
struct A {
A(char cc, int vv=0) : c(cc), v(vv) {}
char c;
int v;
};
class Solution {
public:
int longestValidParentheses(string s) {
int len = s.size();
if (len == 0) return 0;
stack<A> st;
st.push(A(s[0]));
int cnt = 0;
for (int i = 1; i < len; i++) {
cnt = 0;
if (s[i] == '(') st.push(A(s[i]));
else {
while (!st.empty() && st.top().c == '#') {
cnt += st.top().v;
st.pop();
}
if (!st.empty() && st.top().c == '(') {
cnt += 2;
st.pop();
st.push(A('#', cnt));
}
else {
// top().c == '#'
if (cnt > 0) st.push(A('#',cnt));
st.push(A(')'));
}
}
}
cnt = 0;
int mx = 0;
while (!st.empty()) {
if (st.top().c == '#') {
cnt += st.top().v;
if (mx < cnt) mx = cnt;
} else {
cnt = 0;
}
st.pop();
}
return mx;
}
};