牛客-NC49最长的括号字串

描述

给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。

例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
字符串长度：0≤n≤5∗1050≤n≤5∗105
要求时间复杂度 O(n)O(n) ,空间复杂度 O(n)O(n).

示例1

输入：

"(()"

返回值：

2

示例2

输入：

"(())"

返回值：

4

解题思路（优先推荐栈方法，直观易实现）

有效括号的核心是 “匹配”，栈可以精准记录未匹配括号的位置，从而计算有效子串长度，思路如下：

1. 初始化栈：栈中存储括号的索引（而非字符），先压入 -1 作为有效子串的起始基准（处理第一个字符就是 ) 的边界情况）。

2. 遍历字符串：逐个遍历每个字符，记录当前索引 i：

   • 遇到 (：将当前索引 i 压入栈（表示这个左括号等待匹配）。

   • 遇到 )：先弹出栈顶元素（尝试匹配最近的左括号）：

     • 若弹出后栈为空：说明当前 ) 无匹配的 (，将 i 压入栈作为新的基准。
     • 若弹出后栈不为空：当前有效长度 = i - 栈顶元素，用这个值更新最大有效长度。

3. 返回结果：遍历结束后，记录的最大长度即为答案。

完整可运行代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0; // 记录最长有效括号长度
        stack<int> st;  // 存储括号索引，用于计算有效长度
        st.push(-1);    // 初始基准值，处理边界情况（如第一个字符是')'）
        
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                // 左括号：压入当前索引，等待匹配
                st.push(i);
            } else {
                // 右括号：先弹出栈顶（尝试匹配最近的左括号）
                st.pop();
                if (st.empty()) {
                    // 栈空说明当前右括号无匹配，更新基准为当前索引
                    st.push(i);
                } else {
                    // 计算当前有效长度，更新最大值
                    maxLen = max(maxLen, i - st.top());
                }
            }
        }
        
        return maxLen;
    }
};

补充：动态规划方法（可选，进阶思路）

如果想了解另一种常用解法，这里给出动态规划版代码（供参考）：

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
        // dp[i] 表示以s[i]结尾的最长有效括号长度
        vector<int> dp(s.size(), 0);
        
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == ')') {
                // 情况1：前一个字符是'('，直接匹配
                if (s[i-1] == '(') {
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                }
                // 情况2：前一个字符是')'，且前面有匹配的'('
                else if (i - dp[i-1] > 0 && s[i - dp[i-1] - 1] == '(') {
                    dp[i] = dp[i-1] + (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;
                }
                maxLen = max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
};