32. 最长有效括号

题目描述

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

输入输出

1
2
3
4
5
6
7
8
9
10
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

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

输入：s = "())((())"
输出：4

基本思路

  1. 使用栈：

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

  2. 动态规划：

    1. 如果s[i] = ')' 且s[i - 1] = '(' 形如"........()" 可以推出：
      $$
      dp[i] = dp[i-2] + 2
      $$

    2. 如果s[i] = ')' 且s[i - 1] = ')' 形如"........))" 可以推出：

      如果s[ i - dp[i - 1] - 1]='(' 那么
      $$
      dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2
      $$

      1
      2
      3
      4
      5
      6
      7
      模拟理解一下:
                 (  )  (  (  )  )
          index  0  1  2  3  4  5
           dp    0  2  0  0  2  2
      下标2(i-dp[i-1]-1) 与 下标5(i)的两个括号是互相成为一组的
      加上dp[i-1] 即加上下标34的这一对                          ->   +dp[i-1]
      下标1(i-dp[i-1]-2)的括号之前是有两个的 即dp[1]=2           ->   +dp[i-dp[i-1]-2]

  3. 两种方法：时复$O(n)$ 空复$O(n)$

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 使用栈
class Solution {
    public int longestValidParentheses(String s) {
        int res = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '('){
                stack.push(i);
            }
            else{
                stack.pop();
                if(stack.isEmpty()) {
                    stack.push(i);
                }
                res = Math.max(res, i - stack.peek());
            }
        }
        return res;
    }
}

// 动态规划
class Solution {
    public int longestValidParentheses(String s) {
        int res = 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] : 0) + 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] : 0) + 2;
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
}