华为32.最长有效括号

题目描述：
传送门-力扣
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

思路

感觉力扣官方给的几个方法都不是很通俗易懂，这里只记录一个自己觉得比较容易理解的方法，但是时间复杂度比较高。
有效括号总是以‘)’为结尾，因此首先找到第一个‘)’，然后反向查找第一‘(’，这样就找到一对有效括号，同时将这两个位置的括号用其他字符(我用的是0)进行替换。
如：

1. "((()())" 第一次操作后变为((00())"，然后继续向后遍历，找到第二个‘)’，然后反向查找第一个‘(’，两处替换为‘0’，变为"((0000))"，直到遍历到字符串的最后。
2. "(())()))()" -> "(00)()))()" -> "0000()))()" -> "000000))()" -> "000000))00" -> 结束

接下来对处理后的字符串，进行遍历，找到最长子序列，记录其长度即可。

class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, inLen = 0, maxLen = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if(s[i] == ')')
            {
                left = i - 1;
                while(left > 0 && s[left] != '(')
                    left--;
                if(left >= 0 && s[left] == '(')
                {
                    s[left] = '0';
                    s[i] = '0';
                }
            }
        }

        for(int i = 0; i < s.length(); i++)
        {
            if(s[i] == '0')
                inLen++;
            else
                inLen = 0;
            maxLen = max(maxLen, inLen);
        }

        return maxLen;
    }
};