题目描述

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

样例

示例 1:

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

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

算法1

(栈) $O(n)$

栈存储括号的idx,
遇到左括号就往栈里塞idx，遇到右括号就弹出一个idx，然后更新一下结果即可。

时间复杂度

每个括号出入栈一次,$O(n)$。

空间复杂度

每个括号出入栈一次,最坏情况所有括号全部放到栈中，$O(n)$。

参考文献

C++ 代码

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

        return res;
    }
};

算法2

(变量代替栈) $O(n)$

使用变量代替算法1中的栈；
一般来说，题目中只有一种括号可以不用栈，用变量就足够了。

时间复杂度

遍历字符串两次,$O(n)$。

空间复杂度

只是用了常数个变量储存状态，$O(1)$

参考文献

C++ 代码

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

        for (int i = 0; i < n; ++i){
            char c = s[i];
            if (c == '(') ++l;
            else if (c == ')') ++r;
            if (l == r) res = max(res, 2 * l);
            else if (l < r) l = r = 0; 
        }

        l = r = 0;

        for (int i = n - 1; i >= 0; --i){
            char c = s[i];
            if (c == ')') ++r;
            else if (c == '(') ++l;
            if (l == r) res = max(res, 2 * l);
            else if (r < l) l = r = 0;
        }

        return res;
    }
};