题目

image.png

思路

  • 动态规划：
    • 我们用 dp[i] 表示以 i 结尾的最长有效括号；
    • 当 s[i] 为 (,dp[i] 必然等于 0，因为不可能组成有效的括号；那么 s[i] 为 )
      • 当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2；
      • 当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；
        • dp[i-1]表示以i-1结尾的最长有效括号
        • dp[i-dp[i-1]-2]表示以i-dp[i-1]-2结尾的最长有效括号
      • 比如)()(())为例，设此时i=6
      • dp[i-1]表示i为4、5、的括号长度，此时dp[5]=2
      • dp[i-dp[i-1]-2]=dp[2]表示i为1、2的括号长度 dp[2]=2
      • dp[6] = 2(表示dp[i-1]的括号) + 2(表示新增的两个括号) + 2(表示dp[i-dp[i-1]-2]的括号)
      • 本质就是把两个分割有效的括号连在后计算它的长度
  • 栈
    • image.png

  • 正逆向扫描

    • image.png

      代码

      1. //1.动态规划
      2. public int longestValidParentheses(String s) {
      3.    int maxans = 0;
      4.    int[] dp = new int[s.length()];
      5.    for (int i = 1; i < s.length(); i++) {
      6.        if (s.charAt(i) == ')') {
      7.            if (s.charAt(i - 1) == '(') {
      8.                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
      9.            } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
      10.                dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
      11.            }
      12.            maxans = Math.max(maxans, dp[i]);
      13.        }
      14.    }
      15.    return maxans;
      16. }
      18. //2.栈
      19. public int longestValidParentheses(String s) {
      20.    int res = 0;
      21.    Stack<Integer> stack = new Stack<>();
      22.    stack.push(-1);
      23.    for (int i = 0; i < s.length(); i++) {
      24.        if (s.charAt(i) == '(') {
      25.            stack.push(i);
      26.        } else {
      27.            stack.pop();
      28.            if (stack.isEmpty()) {
      29.                stack.push(i);
      30.            } else {
      31.                res = Math.max(res, i - stack.peek());
      32.            }
      33.        }
      34.    }
      35.    return res;
      36. }
      38. //3.正逆向扫描
      39. public int longestValidParentheses(String s) {
      40.    int left = 0, right = 0, maxlength = 0;
      41.    for (int i = 0; i < s.length(); i++) {
      42.        if (s.charAt(i) == '(') {
      43.            left++;
      44.        } else {
      45.            right++;
      46.        }
      47.        if (left == right) {
      48.            maxlength = Math.max(maxlength, 2 * right);
      49.        } else if (right > left) {
      50.            left = right = 0;
      51.        }
      52.    }
      53.    left = right = 0;
      54.    for (int i = s.length() - 1; i >= 0; i--) {
      55.        if (s.charAt(i) == '(') {
      56.            left++;
      57.        } else {
      58.            right++;
      59.        }
      60.        if (left == right) {
      61.            maxlength = Math.max(maxlength, 2 * left);
      62.        } else if (left > right) {
      63.            left = right = 0;
      64.        }
      65.    }
      66.    return maxlength;
      67. }

      最长有效括号