解题思路

对于 最长有效括号子串 问题，常见的两种方法是：

1. 动态规划（DP）
2. 栈（Stack）

方法 1：动态规划（DP）

思路

• 定义 dp[i] 表示 以 i 结尾的 最长有效括号子串的长度。
• 只有 s[i] == ')' 时，才可能形成有效括号：
  1. 如果 s[i-1] == '('
     • dp[i] = dp[i-2] + 2
  2. 如果 s[i-1] == ')'，且 s[i - dp[i-1] - 1] == '('
     • dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2
• 遍历字符串，计算 dp[i]，最终返回 dp 数组的最大值。

时间 & 空间复杂度

• 时间复杂度： O(n)
• 空间复杂度： O(n)

方法 2：使用栈（Stack）

思路

• 使用 栈 记录括号的索引，保证匹配时可以弹出并计算长度：
  1. 如果 s[i] == '('，入栈。
  2. 如果 s[i] == ')'：
     • 如果栈非空，弹出栈顶元素，计算当前有效长度 i - stack[-1]。
     • 如果栈为空，说明当前位置无匹配，更新 start = i + 1。
• 取遍历过程中最大长度作为答案。

时间 & 空间复杂度

• 时间复杂度： O(n)
• 空间复杂度： O(n)

Python 代码

方法 1：动态规划

import sys

def longest_valid_parentheses_dp(s):
    n = len(s)
    if n == 0:
        return 0

    dp = [0] * n  # dp[i] 表示以 s[i] 结尾的最长有效括号长度
    max_length = 0  # 记录最大长度

    for i in range(1, n):
        if s[i] == ')':
            if s[i - 1] == '(':
                dp[i] = (dp[i - 2] if i >= 2 else 0) + 2  # 形如 "()" 的情况
            elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
                dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
            max_length = max(max_length, dp[i])

    return max_length

def main():
    s = sys.stdin.readline().strip()
    print(longest_valid_parentheses_dp(s))

if __name__ == "__main__":
    main()

方法 2：使用栈

import sys

def longest_valid_parentheses_stack(s):
    stack = [-1]  # 记录索引，初始值为 -1
    max_length = 0  # 记录最长有效括号长度

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)  # 左括号入栈
        else:
            stack.pop()  # 右括号尝试匹配
            if stack:
                max_length = max(max_length, i - stack[-1])  # 计算有效长度
            else:
                stack.append(i)  # 记录无效起点

    return max_length

def main():
    s = sys.stdin.readline().strip()
    print(longest_valid_parentheses_stack(s))

if __name__ == "__main__":
    main()

使用input()

s长度可能为0，请使用以下代码

try:
    s = input()
    print(longest_valid_parentheses_stack(s))
except EOFError:
    print(0)

Java 代码

方法 1：动态规划

import java.util.*;

public class Main {
    public static int longestValidParenthesesDP(String s) {
        int n = s.length();
        if (n == 0) return 0;

        int[] dp = new int[n]; // dp[i] 表示以 s[i] 结尾的最长有效括号长度
        int maxLength = 0; // 记录最大长度

        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if(sc.hasNext()){
            String s = sc.next();
            System.out.println(longestValidParenthesesStack(s));
        }
        else{
            System.out.println(0);
        }
        sc.close();
    }
}

方法 2：使用栈

import java.util.*;

public class Main {
    public static int longestValidParenthesesStack(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // 记录索引，初始值 -1
        int maxLength = 0; // 记录最长长度

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i); // 左括号入栈
            } else {
                stack.pop(); // 右括号尝试匹配
                if (!stack.isEmpty()) {
                    maxLength = Math.max(maxLength, i - stack.peek()); // 计算有效长度
                } else {
                    stack.push(i); // 记录无效起点
                }
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if(sc.hasNext()){
            String s = sc.next();
            System.out.println(longestValidParenthesesStack(s));
        }
        else{
            System.out.println(0);
        }
        sc.close();
    }
}

C++ 代码

方法 1：动态规划

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int longestValidParenthesesDP(const string& s) {
    int n = s.size();
    vector<int> dp(n, 0); // dp[i] 记录以 s[i] 结尾的最长有效括号长度
    int max_length = 0;

    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 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;
            }
            max_length = max(max_length, dp[i]);
        }
    }
    return max_length;
}

int main() {
    string s;
    cin >> s;
    cout << longestValidParenthesesDP(s) << endl;
    return 0;
}

方法 2：使用栈

#include <iostream>
#include <stack>

using namespace std;

int longestValidParenthesesStack(string s) {
    stack<int> st;
    st.push(-1);
    int max_length = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            st.pop();
            if (!st.empty()) {
                max_length = max(max_length, i - st.top());
            } else {
                st.push(i);
            }
        }
    }
    return max_length;
}

int main() {
    string s;
    cin >> s;
    cout << longestValidParenthesesStack(s) << endl;
    return 0;
}

题目描述

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

输入描述

输入包含一个字符串 s（$0 \leq |s| \leq 3 \times 10^4$），仅包含 ( 和 )。

输出描述

输出一行，表示最长的有效括号子串的长度。

样例输入 1

(()

样例输出 1

2

样例输入 2

)()())

样例输出 2

4

样例输入 3

()

样例输出 3

2

提示

• s 只包含 ( 和 )。
• 结果是 s 中最长的有效括号子串的长度。