题目描述

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

样例

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

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

算法1

(暴力枚举) $O(n^2)$

1. 每当我们遇到一个 ‘(‘ ，我们把它放在栈顶。
2. 对于遇到的每个 ‘)’ ，我们从栈中弹出一个’(‘
3. 如果栈顶没有 即栈为空，或者遍历完整个子字符串后栈中仍然有元素，那么该子字符串是无效的。
4. 这种方法中，我们对每个偶数长度的子字符串都进行判断，并保存目前为止找到的最长的有效子字符串的长度。

时间复杂度 $O(n^2)$

C++ 代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int maxlen = 0;

        for (int i = 0; i < n; i ++)
        {
            for (int j = i + 2; j < n; j += 2)
            {
                if (isValid(s.substr(i, j - i)))
                  maxlen = max(maxlen, j - i);
            }
        }
        return maxlen;
    }

    bool isValid(string str)
    {
        stack<char> stk;
        int n = str.size();

        for (int i = 0; i < n; i ++)
        {
            if (str[i] == '(') stk.push('(');
            else if (!stk.empty()) stk.pop();
            else return false; 
        }

        return stk.empty();
    }
};

算法2

(栈) $O(n)$

可以在只遍历一次的时间复杂度中求出，我们可以用栈在遍历给定字符串的过程中去判断到目前为止扫描的子字符串的有效性，同时能的都最长有效字符串的长度。

1. 我们首先将 -1−1 放入栈顶(防止前两项正好是’()’)
2. 对于遇到的每个 ‘(‘ ，我们将它的下标放入栈中
3. 对于遇到的每个 ‘)’ ，我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。
   4.注意：在遇到’)’时要判断栈是否为空，若为空则要把’(‘放入栈，否则下一次找到子字符串时栈为空找不到栈顶元素
4. 通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。

时间复杂度 $O(n)$

C++ 代码

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<char> stk;
        int n = s.size();
        int maxlen = 0;

        stk.push(-1);
        for (int i = 0; i < n; i ++)
        {
            if (s[i] == '(') stk.push(i);
            else stk.pop();
            if (stk.empty()) stk.push(i);
            else maxlen = max(maxlen, i - stk.top());
        }
        return maxlen;
    }
};

算法3

(双指针) $O(n)$

利用两个计数器 left 和 right。

1. 首先，从左到右遍历字符串，对于遇到的每个‘(’，增加 left 计算器
2. 否则增加 right 计数器。
3. 每当 left 计数器与 right 计数器相等时，计算当前有效字符串的长度，并且记录最长匹配串的长度
4. 如果 right 计数器比 left 计数器大，将 left 和 right 置零。
5. 然后从右往左，执行一次类似的操作。
6. 如果 left 计数器比 right 计数器大，将 left 和 right 置零。

至于为什么要从左往右和从右往左遍历两次
因为整个括号串中，要么只多余左括号，要么只多余右括号，要么多余的右括号必定在多余的左括号的左侧。

• 当从左到右遍历时，它只能找到「多余的左括号左侧」的有效子串，而「多余的左括号右侧」的有效子串无法找到
• 当从右到左遍历时，只能找到「多余的右括号右侧」的有效子串，而「多余的右括号左侧」的有效子串无法找到

总结：如果从左向右遍历，每当右括号多了的时候，栈就会为空，此时就可以统计之前的有效括号的长度。但是如果是左括号多了，那直到最后也不会栈空，此时也就无法统计中间是否存在有效括号了。因此，从左向右遍历时，一旦遇到右半部分「第一个多余的左括号」，那这个位置后面的串就都无法统计了。

时间复杂度 $O(n)$

C++代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int l = 0, r = 0;
        int maxlen = 0;
        int n = s.size();

        for (int i = 0; i < n; i ++)
        {
            if (s[i] == '(') l ++;
            else r ++;
            if (l == r) maxlen = max(maxlen, l + r);
            else if (l <= r) l = r = 0;
        }

        l = r = 0;

        for (int i = n - 1; i >= 0; i --)
        {
            if (s[i] == '(') l ++;
            else r ++;
            if (l == r) maxlen = max(maxlen, l + r);
            else if (l >= r) l = r = 0;
        }
        return maxlen;
    }
};