32. 最长有效括号

https://leetcode.cn/problems/longest-valid-parentheses/description/

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

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：
输入：s = ""
输出：0
 
提示：
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

• DP解法: 使用数组

class Solution {
public:
    int longestValidParentheses(string s) {
        int count = 0;
        vector<int> dp(s.size() + 1);
        int maxLen = 0;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == '('){
                ++count;
            }else if(count != 0){
                do {
                    auto len = dp[i] + 2;
                    ++i;
                    auto preIndex = i  - len;
                    if(dp[preIndex] != 0){
                        len += dp[preIndex];
                    }
                    dp[i] = len;
                    maxLen = max(maxLen,len);
                    --count;
                } while (count > 0 &&  i < s.size() && s[i] == ')');
                --i;
            }
        }
        return maxLen;
    }
};



/*
int main()
{
    Solution sln;
    assert(sln.longestValidParentheses("()()((())))") == 10); //10
    assert(sln.longestValidParentheses("()()((((())))") == 8); //10
    assert(sln.longestValidParentheses("(()())") == 6); //6
    assert(sln.longestValidParentheses("((((()()") == 4); //4
    return 0;
    
}
*/

• DP解法: 使用栈

class Solution {
public:
    inline int adjustLen(int preIndex,int len,stack<pair<int, int>> &dp){
        auto top = dp.top();
        if(top.first == preIndex){
            len += top.second;
            dp.pop();
        }
        return len;
    }
    int longestValidParentheses(string s) {
        int count = 0;
        stack<pair<int, int>> dp;
        dp.push({-1,0});
        int maxLen = 0;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == '('){
                ++count;
            }else if(count != 0){
                do {
                    int len = 2;
                    len = adjustLen(i, len, dp);
                    ++i;
                    len = adjustLen(i - len, len, dp);
                    dp.push({i,len});
                    maxLen = max(maxLen,len);
                    --count;
                } while (count > 0 &&  i < s.size() && s[i] == ')');
                --i;
            }
        }
        return maxLen;
    }
};

/*
int main()
{
    Solution sln;
    assert(sln.longestValidParentheses("()()((())))") == 10); //10
    assert(sln.longestValidParentheses("()()((((())))") == 8); //10
    assert(sln.longestValidParentheses("(()())") == 6); //6
    assert(sln.longestValidParentheses("((((()()") == 4); //4
    return 0;
}
*/

• 官方解法: 空间复杂度为O(1)

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

/*
int main()
{
    Solution sln;
    assert(sln.longestValidParentheses("()()((())))") == 10); //10
    assert(sln.longestValidParentheses("()()((((())))") == 8); //10
    assert(sln.longestValidParentheses("(()())") == 6); //6
    assert(sln.longestValidParentheses("((((()()") == 4); //4
    return 0;
    
}
*/