Longest Valid Parentheses（最长的括号匹配）【面试算法leetcode】

题目：

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.

之前写过一题类似的，是用栈去维护括号匹配的做法，因此想有没其他的做法。

贪心的思想，和上一题类似，用双指针扫描，维护满足l>=r的字符串。

当r>l时，移动i指针知道满足r==l并输出长度。

但这么做无法计算当l>r时，j已经扫描到字符结尾时最长匹配，例如(()的情况。

我想到的解决办法是吧字符串反转，因为括号反转后不改变之间的匹配，在用同样的方式扫描一遍，正好能考虑出剩余的情况。

class Solution {public:    int longestValidParentheses(string s) {        int i,j,l=0,r=0,maxx=0;        for(i=0,j=0;j<s.length();++j)        {            if(s[j]=='(')l++;            else r++;            while(r>l&&i<=j)            {                if(s[i++]=='(')--l;                else --r;            }            if(r==l)maxx=max(maxx,j-i+1);        }           reverse(s.begin(),s.end());        l=r=0;        for(i=0,j=0;j<s.length();++j)        {            if(s[j]==')')l++;            else r++;            while(r>l&&i<=j)            {                if(s[i++]==')')--l;                else --r;            }            if(r==l)maxx=max(maxx,j-i+1);        }         return maxx;    }};