动态规划 32. 最长有效括号
2023-02-26 09:46:33 时间
动态规划 32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"示例 3：
输入：s = ""
输出：0提示：
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
代码
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;
}
}