动态规划 32. 最长有效括号

Mashiro

2022 年 12 月 21 日

450 次浏览

暂无评论

1370字数

算法

# 动态规划   32. 最长有效括号

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

示例 1：

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

示例 2：

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

示例 3：

```
输入：s = ""
输出：0
```

提示：
`0 <= s.length <= 3 * 104`
`s[i]` 为 `'('` 或 `')'`

## 代码

```java
package ski.mashiro.leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class _32 {
    /**
     * 32. 最长有效括号
     * <p>
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     */
    public static void main(String[] args) {
        System.out.println(longestValidParentheses2("(()())"));
    }
//	  dp
    public static int longestValidParentheses(String s) {
        int rs = 0;
//        建立表格，表示以下标 i 字符结尾的最长有效括号的长度
        int[] dp = new int[s.length()];
//        一个字符不可能成为括号对
        for (int i = 1; i < s.length(); i++) {
//            如果 i 处为 ')'
            if (s.charAt(i) == ')') {
//                如果 ')' 前一个是 '('
                if (s.charAt(i - 1) == '(') {
//                    判断是否有可能是 ()()() 这种情况
                    if (i < 2) {
//                    如果 i < 2 ，说明前面没有有效括号对
                        dp[i] = 2;
                    } else {
//                    是 ()()() 这种情况
//                    即 ---|   i = 3 和 5 时，前面有一对有效括号
//                       -|-|  这时就要加上前面的长度
                        dp[i] = dp[i - 2] + 2;
                    }
//                         判断是否不是 ())       连续两个 ')', dp[i - 1] 前一个 ')' 合法, -1 找到括号对的前一个
                } 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;
//                    判断情况 (()..()) 这样末尾 i 为奇数, 中间括号对为偶数，且两者差为 1
                    if (i - dp[i - 1] < 2) {
                        dp[i] = dp[i - 1] + 2;
                    } else {
                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                    }
                }
                rs = Math.max(rs, dp[i]);
            }
        }
        return rs;
    }

//	  栈
    public static int longestValidParentheses2(String s) {
//        栈顶元素为最后一个无法匹配的 ')' 的值
        Deque<Integer> stack = new LinkedList<>();
        int rs = 0;
//        边界条件
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            }
            if (s.charAt(i) == ')') {
//                先弹出   因为栈内必有一个元素 即栈顶
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    rs = Math.max(rs, i - stack.peek());
                }
            }
        }
        return rs;
    }
}
```

最后修改：2022 年 12 月 21 日