📃 题目描述

题目链接：32. 最长有效括号 (opens new window)

🔔 解题思路

自己动手画个图就能明白了，先空着，后面我会补上

class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        // 以 s[i] 结尾的最长有效括号子串的长度
        int[] dp = new int[len];

        int res = 0;

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

            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：