32. 最长有效括号

📝 题目描述

给你一个仅由 '(' 和 ')' 组成的字符串 s，找出最长 有效括号子串 的长度。

有效括号指：左右括号必须严格成对匹配，如：

()   (())   ()()

---

📌 示例

示例 1

输入：

s = "(()"

输出：

2

解释：最长有效括号子串是 "()"

示例 2

输入：

s = ")()())"

输出：

4

解释：最长有效括号子串是 "()()"

示例 3

输入：

s = ""

输出：

0

---

🚀 最优解：栈 + 标记数组（O(n)）

🔍 思路解析

我们想找 哪些位置是有效的括号。

策略：

1. 遍历字符串，用栈存储 '(' 的下标。
2. 每当遇到 ')' 且可以匹配（栈非空），就把这两个位置都标记为 true：
   • dp[leftIndex] = true
   • dp[rightIndex] = true
3. 最终所有连续的 true 段落，就是有效括号区间。
4. 找最大连续 true 的长度即可。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取字符串
        String s = scanner.nextLine();

        Solution solution = new Solution();
        int result = solution.longestValidParentheses(s);

        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        Stack<Integer> stack = new Stack<>();
        boolean[] dp = new boolean[n];  // dp[i] = true 表示该位置在有效括号中

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    int index = stack.pop();
                    dp[index] = true;
                    dp[i] = true;
                }
            }
        }

        // 找最长连续的 true 的区间
        int max = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i]) {
                cur++;
                max = Math.max(max, cur);
            } else {
                cur = 0;
            }
        }

        return max;
    }
}

---

🧠 通俗易懂解释

你可以把这题理解成：

哪些位置是合法的括号？找出它们最长连续的一段。

例如：

) ( ) ( ) )
0 1 2 3 4 5

匹配成功的位置标记为 true：

false true true false true true

这些 true 区段表示有效括号片段：

• [1,2] → "()"
• [4,5] → "()"

最长连续 true 的长度就是答案。

---

⏱ 时间复杂度

O(n)

• 单次遍历字符串（入栈、出栈）
• 再遍历一次 dp 数组统计连续长度

---

💾 空间复杂度

O(n)

• 栈最多存储 n 个下标
• dp 数组占用 n 空间

---