Longest Valid Parentheses

来源：Leetcode

原帖：http://oj.leetcode.com/problems/longest-valid-parentheses/

题目：
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.

代码：

 class Solution {  
 public:  
   int longestValidParentheses(string s) {  
     stack<int> lefts;  
     int maxlen = 0, last = -1; // last index: 保存的是  
     for (int i = 0; i < s.size(); i++){  
       if (s[i] == '(') {  
         lefts.push(i);  
       } else {  
         if (lefts.empty())  
           last = i;  
         else {  
           lefts.pop();  
           if (lefts.empty())  
             maxlen = max(maxlen, i-last);  
           else  
             maxlen = max(maxlen, i-lefts.top());  
         }    
       }  
     }  
     return maxlen;  
   }  
 };