题目

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

示例 1：

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

示例 3：

输入：s = “”
输出：0

提示：

0 <= s.length <= 3 * 10^4
s[i] 为 ‘(‘ 或 ‘)’

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

方法一：参考「热评」的解法，先利用栈将无法匹配的括号标识出来，比如可以将该下标位置为1，然后就转化为了求连续最长的0的长度，见代码一。

方法二：动态规划，dp[i]表示以i位置结尾的最长的有效括号长度，首先i处的字符必须是右括号，接下来讨论dp[i]值为多少，如果i-1处为左括号，那么dp[i]=dp[i-1]+2，这一点好理解，如果i-1处不是左括号，就需要找到和i这个右括号匹配的左括号（也可能不存在匹配的左括号），这个左括号如果存在的话，一定在和i-1匹配的左括号的左边，例如，如果dp[i-1]为2，那么i处往前dp[i-1]+1即往前3位就是要找的左括号（仍然要注意是可能为左括号），下标即i-dp[i-1]-1，以这个左括号左边的括号结尾的dp[i-dp[i-1]-2]加上i-dp[i-1]-1到i的长度就是dp[i]了，写成公式就是dp[i]=dp[i-dp[i-1]-2]+dp[i-1]+2。自己也觉得描述的很是乱，看代码吧还是。

代码

代码一 栈+数组

  1. class Solution {
  2.     public int longestValidParentheses(String s) {
  3.         int n = s.length();
  4.         int[] arr = new int[n];
  5.         Deque<Integer> stack = new ArrayDeque<>();
  6.         for (int i = 0; i < n; i++) {
  7.             if (s.charAt(i) == '(') {
  8.                 stack.push(i);
  9.             } else {
  10.                 if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
  11.                     stack.poll();
  12.                 } else {
  13.                     // 当前右括号无法匹配
  14.                     arr[i] = 1;
  15.                 }
  16.             }
  17.         }
  18.         // 最后栈中为未匹配的左括号
  19.         while (!stack.isEmpty()) {
  20.             arr[stack.poll()] = 1;
  21.         }
  22.         // 将无法匹配的括号都标记为1，最后就是求最长的连续的0长度
  23.         int ans = 0;
  24.         int cnt = 0;
  25.         for (int i = 0; i < n; i++) {
  26.             if (arr[i] == 0) {
  27.                 cnt++;
  28.                 ans = Math.max(ans, cnt);
  29.             } else {
  30.                 cnt = 0;
  31.             }
  32.         }
  33.         return ans;
  34.     }
  35. }

代码二 DP

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] arr = new int[n];
        int ans = 0;
        // dp[i]表示以第i位结尾的最长有效括号的长度，i属于[1,n]
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) == ')') {
                if (s.charAt(i - 2) == '(') {
                    dp[i] = dp[i - 2] + 2;
                    // i 往前 dp[i - 1] + 1 位是i匹配的左括号，在dp中下标为i - dp[i - 1] - 1，在s中还需要偏移一个下标，因此对于s来说是i - dp[i - 1] - 2
                } else if (i - dp[i - 1] - 2 >= 0 && s.charAt(i - dp[i - 1] - 2) == '(') {
                    // dp[i-1]+2是i - dp[i - 1] - 1到i的长度，dp[i - dp[i - 1] - 2]是以i - dp[i - 1] - 1的左边括号结尾的最长有效长度
                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
                }
                ans = Math.max(ans, dp[i]);
            }
        }
        return ans;
    }
}