题目描述

解题思路

dp

dp[i]的含义：在s字符串中索引为i的字符匹配的最长有效括号字串。
递推公式：

• 如果s[i] = ‘)’ , s[i-1] = ‘(‘ , dp[i] = dp[i - 2] + 2;
• 如果s[i] = ’)‘, s[i - 1] = ‘)’ , dp[i - dp[i - 2] - 1] = ‘(‘, dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

解释一下：如果当前是 ) ，前一个字符是 ( ，此时就可以匹配，所以为dp[i-2] + 1。
第二个如何推出来的？如果当前字符和前一个字符都是 )) ，此时我们需要考虑是不是中间都为匹配过的，我们要找到有没有和我们 ) 这个匹配的 ( ，所以需要判断 dp[i - dp[i - 2] - 1]（注意减去中间匹配的进行判断） 是否为 ( ，如果不是，那也不匹配，如果是，那么 dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 。
为啥是3部分呢？
dp[i - 1] 表示中间匹配的，dp[i - dp[i - 1] - 2] 表示dp[i - dp[i - 1] - 1]前面匹配的子串有多少（没有匹配的就为0），2是刚刚判断的2个字符。
代码如下：注意判断和防止数组越界。
动图参照官解法：https://leetcode.cn/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

// dp
// 如果s[i] = ')' , s[i-1] = '(' , dp[i] = dp[i - 2] + 2;
// 如果s[i] = ’)‘, s[i - 1] = ')' , dp[i - dp[i - 2] - i] = '(', dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2]  + 2
public int longestValidParentheses(String s) {
    int maxAns = 0;
    int[] dp = new int[s.length()];
    char[] array = s.toCharArray();
    for (int i = 1; i < array.length; i++) {
        if (array[i] == ')') {
            if (array[i - 1] == '(') {
                dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && array[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
        }
        maxAns = Math.max(maxAns, dp[i]);
    }
    return maxAns;
}

栈

动图参照官解法：https://leetcode.cn/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
很巧妙的做法：存储的是下标，栈底始终为最后一个没有被匹配的的右括号的下标，那么我们在匹配之后根据栈是否为空来判断，如果为空，那么此时没有匹配的，所以我们需要放入右括号的索引在栈底，如果不为空，那么可以直接求匹配的最大子串。

// 栈
public int longestValidParentheses(String s) {
    // 存储下标，栈底始终为最后一个没有被匹配的的右括号的下标
    Stack<Integer> stack = new Stack<>();
    // 初始化-1进去，满足一开始栈为空的情况
    stack.push(-1);
    int res = 0;
    char[] array = s.toCharArray();
    for (int i = 0; i < array.length; i++) {
        if (array[i] == '(') {
            stack.push(i);
        } else if (array[i] == ')') {
            // 表示匹配
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                res = Math.max(res, i - stack.peek());
            }
        }
    }
    return res;
}

贪心优化空间复杂度为O（1）

动图参照官解法：https://leetcode.cn/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
向右遍历，进行匹配，但会丢失(()的情况，而()))不会丢失，因为右括号大于左括号会直接重置。所以还需要向左遍历一次。

// 不开辟额外的空间
public int longestValidParentheses(String s) {
    int left = 0, right = 0, maxLength = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') left++;
        else right++;
        if (left == right) maxLength = Math.max(maxLength, 2 * right);
        else if (right > left) left = right = 0;
    }
    left = right = 0;
    for (int i = s.length() - 1; i > 0; i--) {
        if (s.charAt(i) == '(') left++;
        else right++;
        if (left == right) maxLength = Math.max(maxLength, 2 * left);
        else if (left > right) left = right = 0;
    }
    return maxLength;
}