leetcode32：最长有效括号

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

/*
    栈中记录每个左括号的位置，便于计算最长有效括号子串的长度。
    1.遇到左括号
        将其索引压入栈中，这是一个未匹配的左括号。
    2.遇到右括号
        弹出栈顶元素（找到了与当前右括号匹配的左括号），检查栈是否为空。
        如果栈为空，
            说明没有匹配的左括号，此时将右括号的索引压入栈中作为新的基准。
        如果栈不为空，
            则当前右括号与匹配的左括号之间构成了有效的括号子串，计算长度。

    时间复杂度：O(n)
        n 是字符串的长度。遍历字符串一次。
    空间复杂度：O(n)
        在最坏情况下，栈的大小会达到 n。
*/
class Solution_0 {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1); // 初始无效位置
        int res = 0;

        for (int i = 0; i < s.size(); 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;
    }
};

/*
    状态表示：
        f[i] 表示以下标 i 结尾的最长有效括号的长度。
    状态计算：
        1. s[i] = ')' && s[i−1] = '('，
            即字符串形式为 "...()"
            f[i] = f[i−2] + 2
        2. s[i] = ')' && s[i−1] = ')' && s[i−f[i−1]−1] = '(，
            即字符串形式为 "...((...))"
            f[i] = f[i−1] + 2 + f[i−f[i−1]−2]
    初始化：
        初始化为 0，默认情况下，没有有效括号子串。
    遍历顺序：
        从前向后遍历字符串求解，每次检查相邻的两个字符。
    答案：
        f 数组中的最大值。

   时间复杂度：O(n)
       其中 n 为字符串的长度。
       遍历整个字符串一次，求出 dp 数组。
   空间复杂度：O(n)
*/
class Solution_1 {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> f(n, 0); // 初始化为 0
        int res = 0; // 最长有效括号子串的长度

        for (int i = 1; i < n; i++) {
            if (s[i] == ')') { // 右括号才可能构成有效括号对
                if (s[i-1] == '(') {
                    // 前一个是 '('，直接构成 "()"
                    f[i] = (i >= 2 ? f[i-2] : 0) + 2;
                } else if (i-f[i-1] > 0 && s[i-f[i-1]-1] == '(') {
                    // 前一个是 ')', 形成嵌套括号结构
                    f[i] = f[i-1] + 2;
                    if (i-f[i-1]-2 >= 0) {
                        f[i] += f[i-f[i-1]-2]; // 加上前一个有效子串
                    }
                }
                res = max(res, f[i]); // 更新最大值
            }
        }
        
        return res;
    }
};

/*
    两次线性扫描，贪心地考虑以当前下标结尾的有效括号长度。

    两个计数器 left 和 right，从左向右遍历字符串。
    left 等于 right 时，计算当前有效字符串的长度，并记录当前找到的最长子字符串；
    left 小于 right 时，将 left 和 right 计数器同时变回 0。
    右括号数量多于左括号数量时，之前的字符不再考虑，重新从下一个字符开始计算，
    但这样会漏掉一种情况，左括号的数量大于右括号的数量，即 (() ，这时最长有效括号无法求出。
    
    解决方法：
    从右向左遍历的方法计算，判断条件反过来：
    left 等于 right 时，计算当前有效字符串的长度，并记录当前找到的最长子字符串；
    left 大于 right 时，将 left 和 right 计数器同时变回 0。

    时间复杂度：O(n)
        遍历两次字符串。
    空间复杂度：O(1)
*/
class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        int left = 0, right = 0;

        // 从左向右遍历
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                left++;
            } else if (s[i] == ')') {
                right++;
            }

            if (left == right) {
                res = max(res, right*2);
            } else if (left < right) {
                left = right = 0;
            }
        }

        left = right = 0;
        // 从右向左遍历
        for (int i = s.size()-1; i >= 0; i--) {
            if (s[i] == '(') {
                left++;
            } else if (s[i] == ')') {
                right++;
            }

            if (left == right) {
                res = max(res, left*2);
            } else if (left > right) {
                left = right = 0;
            }
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = {
        "(()",
        ")()())",
        ""
    };

    for (auto& str : s_cases) {
        cout << "Input: \"" << str << "\"" << endl;
        int result = solution.longestValidParentheses(str);
        cout << "Output: " << result << endl;
    }

    return 0;
}