本来以为没必要用栈，代码如下：
class Solution { public: int longestValidParentheses(string s) { int stack = 0; int length=0,max=0; for(int i=0;i<s.length();i++) { if(s[i]==‘(‘) stack++; if(s[i]==‘)‘) { if(stack>0) { stack--; length+=2; if(length>max) max=length; } else length=0; } } return max; } };
之前的思路是遇到左括号就标志变量+1，遇到右括号就-1，如果遇到右括号而且标志变量为0就说明出现了不匹配的情况。但是这样没有记住之前的信息，遇到左括号无法匹配的情况就没辙了，比如"()(()"
用栈把左括号的位置都记录下来，用变量记录不匹配的位置，初始化为-1并入栈，因此遇到右括号时，如果栈的大小=1就说明出现不匹配的情况，将新的不匹配位置入栈。这种办法比起刚开始的想法的好处是可以 记录左括号的位置，就不会出现之前的错误了。
class Solution { public: int longestValidParentheses(string s) { stack<int> pstack; pstack.push(-1); int length=0,max=0; for(int i=0;i<s.length();i++) { if(s[i]==‘(‘) pstack.push(i); if(s[i]==‘)‘) { if(pstack.size()>1) { pstack.pop(); length = i - (int)pstack.top(); if(length>max) max=length; } else { pstack.pop(); pstack.push(i); } } } return max; } };
leetcode32. Longest Valid Parentheses
原文：http://www.cnblogs.com/tonychen-tobeTopCoder/p/5178318.html