最长有效括号

给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。

提示：

• 0 <= s.length <= 3 * 10^4
• s[i]为'('或')'

32.最长有效括号

栈

想起那天早上，数据结构的老师和我们说，我和你们没有共同语言判断括号用栈。于是小黎看到这题就哼哧哼哧地用了栈，美美错了。

之后寻思啊，这个栈里面放的都是左括号，感觉信息量很低啊，不如存放下标，这样就能计算长度了。

中间走的弯路忘记了，反正就是个考虑不全的憨憨的思考过程

最后整理出了如下思路：

• 用一个变量start存放合法字符串的开始下标
• 遍历的过程中，如果遇到左括号，就将其下标入栈
• 如果遇到右括号，且此时栈为空，说明没有可与之匹配的左括号，字符串不合法，将start设在该下标的后一个
• 如果遇到右括号，且此时栈不为空，则弹出栈顶数据。如果弹出栈顶之后说明从start到目前下标已经匹配完成，可以记录从start到目前的长度，来更新答案。如果弹出之后栈不为空，说明仍有左括号未匹配，则此时的长度为栈顶未匹配的左括号下标之后到目前下标的距离，以此更新答案。

说完啦！上代码！

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> sta;
        int n = s.size();
        int ans = 0;
        int start = 0;
        for(int i = 0; i < n; ++i){
            if(s[i] == '('){
                sta.push(i);
            }else if(sta.empty()){
                start = i + 1;
            }else{
                sta.pop();
                if(sta.empty()){
                    ans = max(ans, i - start + 1);
                }else{
                    ans = max(ans, i - sta.top());
                }
            }
        }
        return ans;
    }
};

两次遍历

就是弄两个变量，从左至右遍历，分别记录左括号和右括号的个数。当左括号等于右括号时，记录当前字符长度，当右括号多余左括号时重开重新置零开始计数。

这样对于左括号多余右括号的字符串是无法计数的，所以考虑再从右往左遍历。和之前思路相似，当左右括号数目相等时，记录当前长度，当左括号数目大于右括号数目时重新置零开始计数。

class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = (int)s.length() - 1; i >= 0; i--) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
};

相比起栈的做法，相当于是用时间换空间了吧