题目描述

题目链接

https://leetcode.cn/problems/longest-valid-parentheses/

思路

1. 动态规划

我们定义表示以下标字符结尾的最长有效括号的长度。我们将数组全部初始化为。显然有效的子串一定以结尾，因此我们可以知道以结尾的子串对应的值必定为，因为它肯定不是一个有效的子串，我们只需要求解在数组中对应位置的值。

我们从前往后遍历字符串求解值，我们每两个字符检查一次：

• 且，也就是字符串形如，我们可以推出：

  

我们可以进行这样的转移，是因为结束部分的是一个有效的子字符串，并且将之前有效子字符串的长度增加了。

• 且，也就是字符串形如，我们可以推出：

  如果，那么

我们考虑如果倒数第二个是一个有效子字符串的一部分（记作），对于最后一个，如果它是一个更长子字符串的一部分，那么它一定有一个对应的，且它的位置在倒数第二个所在的有效子字符串的前面（也就是的前面）。因此，如果子字符串的前面恰好是，那么我们就用加上的长度（）去更新。

同时，我们也会把有效子串之前的有效子串的长度也加上，也就是再加上。因为可能会存在以下这种情况：

最后的答案即为数组中的最大值。具体代码实现如下：

public int longestValidParentheses(String s) {
    int maxLen = 0;
    int[] dp = new int[s.length()];
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            // 判断其前一个字符
            if (s.charAt(i - 1) == '(') {
                // ...()
                dp[i] = i >= 2 ? dp[i - 2] + 2 : 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] + 2 : 2;
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
    }
    return maxLen;
}

• 时间复杂度：，其中为字符串的长度。我们只需遍历整个字符串一次，即可将数组求出来。
• 空间复杂度：。我们需要一个大小为的数组。

  2. 栈

  撇开方法一提及的动态规划方法，相信大多数人对于这题的第一直觉是找到每个可能的子串后判断它的有效性，但这样的时间复杂度会达到，无法通过所有测试用例。我们知道栈在处理括号匹配有着天然的优势，因此通过栈，我们可以在遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性，同时也能得到最长有效括号的长度。

由于我们计算的是有效括号的长度，因此栈中元素存储的是下标值。具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

• 对于遇到的每个，我们将它的下标放入栈中。
• 对于遇到的每个，我们先弹出栈顶元素表示匹配了当前右括号：
  • 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新「最后一个没有被匹配的右括号的下标」。
  • 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」。

我们从前往后遍历字符串并更新答案即可。需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为的元素。 具体代码实现如下：

public int longestValidParentheses2(String s) {
    int maxLength = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
        // 遇到左括号入栈
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            // 遇到右括号先出栈
            stack.pop();
            if (stack.empty()) {
                // 记录最后一个没有被匹配的右括号的下标
                stack.push(i);
            } else {
                // 更新最长有效括号
                maxLength = Math.max(maxLength, i - stack.peek());
            }
        }
    }
    return maxLength;
}

• 时间复杂度：，是给定字符串的长度。我们只需要遍历字符串一次即可。
• 空间复杂度：。栈的大小在最坏情况下会达到，因此空间复杂度为。

  3. 双向遍历

  实际上，我们也可以不使用栈来判断括号有效性。具体做法类似：【22】括号生成 里的实现，通过维护左括号和右括号的数量来判断括号是否有效。这样的话，空间复杂度就能降到。

具体地，我们利用两个计数器和。首先，我们从左到右遍历字符串，对于遇到的每个，我们增加计数器，对于遇到的每个，我们增加计数器。每当计数器与计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当计数器比计数器大时，我们将和计数器同时变回。

这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 ，这种时候最长有效括号是求不出来的。解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：

• 当比计数器大时，我们将和计数器同时变回 00。
• 当与计数器相等时，计算当前有效字符串的长度，并记录目前为止找到的最长子字符串。

这样我们就能涵盖所有情况从而求解出答案。具体代码实现如下：

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;
}

• 时间复杂度：，其中为字符串长度。我们只要正反遍历两边字符串即可。
• 空间复杂度：。我们只需要常数空间存放若干变量。