[Leetcode][第32题][JAVA][最长有效括号][动态规划][栈][正向逆向结合]

【问题描述】[困难]

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

【解答思路】

1. 动态规划

动态规划流程 第 1 步：设计状态 dp[i] 表示以下标 ii 字符结尾的最长有效括号的长度 第 2 步：状态转移方程 “……()”：s[i]=‘)’ 且 s[i−1]=‘(’ dp[i]=dp[i−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 第 3 步：考虑初始化 注意 边界问题 i>=0 第 4 步：考虑输出 maxans = Math.max(maxans, dp[i]); 时间复杂度：O(N) 空间复杂度：O(N)

public class Solution { public int longestValidParentheses(String s) { int maxans = 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; } maxans = Math.max(maxans, dp[i]); } } return maxans; } }

2. 栈

辅助 不符合条件时要中断 遇到“（”把当前遍历i下标入栈 遇到“）”出栈 空时证明子串中断 非空 计算深度 i - stack.peek() 时间复杂度：O(N) 空间复杂度：O(N)

public class Solution { public int longestValidParentheses(String s) { int maxans = 0; Stack<Integer> stack = new Stack<>(); stack.push(-1); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); } else { stack.pop(); if (stack.empty()) { stack.push(i); } else { maxans = Math.max(maxans, i - stack.peek()); } } } return maxans; } }

3. 正向逆向结合

时间复杂度：O(N) 空间复杂度：O(1)

public class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, maxlength = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * right); } else if (right > left) { left = right = 0; } } left = right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * left); } else if (left > right) { left = right = 0; } } return maxlength; } }

【总结】

1.动态规划流程

第 1 步：设计状态 第 2 步：状态转移方程 第 3 步：考虑初始化 第 4 步：考虑输出 第 5 步：考虑是否可以状态压缩

2.栈 计算长度的题目 可以以字符串位置下标入栈 引入辅助栈（长度开始的下标）

3. 正向逆向结合 好方法 好思想 灵活运用

转载链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/