本文共 1287 字，大约阅读时间需要 4 分钟。

给一个只包含 '(' 和 ')' 的字符串，找出最长的有效（正确关闭）括号子串的长度。

对于 "(()"，最长有效括号子串为 "()" ，它的长度是 2。

另一个例子 ")()())"，最长有效括号子串为 "()()"，它的长度是 4。

思路：设置一个变量l，表示当前未被匹配的左括号数目。设置一个vector<int>re来记录字符匹配情况，我们用-1代表左括号，1代表右括号。

每当遇到左括号的时候：就将-1压入re中，并且l++。

每当遇到右括号的时候，看一下l的大小：

1、如果l>0，说明前面有和它相匹配的左括号，然后我们就去re中找离它最近的-1，就是和它相匹配的那个左括号。这个时候有两种情况，一个是re.back()就是-1，我们就把re.back()元素pop出来，然后压进去2，表示有两个字符是匹配的。另外一种情况是它前面有一些2,4,6这样的整数（有一些匹配字符），再前面才是-1。这种情况下，我们就要不断的把这些元素pop出来，加起来，直到找到-1，再将刚才的和加上2，然后再压入re中。同时l-1，说明未匹配的左括号数目少了1.

2、如果l=0,说明它前面没有和它相匹配的左括号，将1压入re中。

最后我们对这个re进行一次遍历，寻找最长有效括号数目，这里面的数字应该是被1，或者是-1分隔开的一些区间。每一个区间连续和的最大值即为所求。

class Solution {public:    int longestValidParentheses(string s) {        vector
   
    re;        int l = 0, ans = 0;        for (auto x : s){            if (x == '(') {                ++l;                re.push_back(-1);            }            if (x == ')') {                if (l>0){                    int temp=0;                    while (re.back() != -1){                        temp += re.back();                        re.pop_back();                    }                    re.pop_back();                    l--;                    re.push_back(temp += 2);                }                else{                    re.push_back(1);                }            }        }        for (int i = 0; i
   

转载地址：http://uhabi.baihongyu.com/