32. 最长有效括号
题目链接：https://leetcode.cn/problems/longest-valid-parentheses/
解题思路：
暴力递归
定义递归函数：match(char[] s, int end)，表示以s[end]结尾的最长有效括号子串，
递归的终止条件
end<=0 或者 s[end]='('，返回0，因为有效括号子串必须以 ')" 结尾
end ==1，如果s[end-1]=='(' && s[end] ==')' 返回2，否则返回0
经过终止条件后，现在s[end] == ')'
如果s[end-1] == '('，显然可以和s[end]组合成一个有效括号，以s[end]结尾的最长有效括号的长度也就是以s[end-2]结尾的最长有效括号长度+2，返回match(s,end-2)+2
否则，也就是s[end]==')'，s[end-1] == ')'，这个时候需要先找到以s[end-1]结尾的最长有效括号长度，
比如s="()(()())"：此时先找到以倒数第二个红色 ')' 结尾的最长有效括号，也就是"(()())"，长度为4，
接着需要将最后一个红色的 ')' s[end]，与其前面第5个括号s[end-5]匹配（跳过已经匹配过的括号）：s="()(()())"
因为s[end-5]='('，可以与s[end]组合成一个有效的括号，此时s[end-5]之前还有括号，这些括号还能组合有效的括号，还需要计算以s[end-match(s,end-1)-1]结尾的有效括号长度，所以应该返回：match(s,end-1)+2+match(s, end - match(s,end-1) - 1 )
如果s[end-5]=')'，不能与s[end]=')'组合成一个有效的括号，返回0
通过递归方程可以找到所有以s[index]结尾的最长有效括号的长度，从前往后遍历，记录最长的即可
AC代码：
class Solution {public static int longestValidParentheses(String s) {int result = 0;char[] str = s.toCharArray();for (int i = 0; i < s.length(); i++) {result = Math.max(result, match(str, i));}return result;}//以s[end]结尾的最长有效括号长度public static int match(char[] s, int end) {if (end <= 0 || s[end] == '(') {return 0;}if (end == 1) {if (s[end - 1] == '(' && s[end] == ')') {return 2;} else {return 0;}}if (s[end - 1] == '(') {return match(s, end - 2) + 2;}//s[end-1] ==')' s[end] ==')'//preLength表示以s[end-1]结尾的最长有效括号长度int preLength = match(s, end - 1);//except表示s[end]想要匹配的下一个括号索引int except = end - preLength - 1;if (except >= 0 && s[except] == '(') {return preLength + 2 + match(s, except - 1);} else {return 0;}}
}
动态规划：根据上面的递归求解直接转换为动态规划的方式，dp[i]保存以s[i]结尾的最大有效括号长度
也就是令代码中dp[end]=match(s,end)，然后根据当前递归会进入哪些递归方程，推导出相应的dp状态转移
AC代码
class Solution {public static int longestValidParentheses(String s) {if (s.length() == 0 || s.length() == 1) {return 0;}int[] dp = new int[s.length()];int result = 0;if (s.charAt(0) == '(' && s.charAt(1) == ')') {dp[1] = 2;result = 2;}for (int i = 2; i < s.length(); i++) {if (s.charAt(i)=='('){dp[i]=0;continue;}if (s.charAt(i-1) == '(') {dp[i] = dp[i - 2] + 2;}int preLength = dp[i - 1];int except = i - preLength - 1;if (except >= 0 && s.charAt(except) == '(') {if (except - 1 >= 0) {dp[i] = preLength + 2 + dp[except - 1];} else {dp[i] = preLength + 2;}} else {dp[i] = 0;}result = Math.max(result, dp[i]);}return result;}
}
时间从9ms优化到1ms
栈的方式求解：
因为有效的括号一定以 ")"结尾，所以定义栈底元素为最后一个没有被匹配到的 ")" 的下标，初始时，因为栈为空，当第一个入栈的元素为 "("时，并不满足栈底元素为最后一个没有被匹配到的 ")"，所以为了统一处理，初始时向栈底放入一个-1的元素
从前往后遍历字符串
每遇到一个 "(" ,就将其下标入栈
每遇到一个 ")"，就先弹出栈顶元素（因为初始时放入的是一个-1）
如果栈为空，说明当前的 ")"没有被匹配到，将其下标放入栈中更新栈底元素为最后一个没有被匹配到的 ")" 的下标
如栈不为空，说明有一个"("与之匹配，当前 ")"的小标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度
AC代码
class Solution {public static int longestValidParentheses(String s) {int result = 0;if (s.length() == 0 || s.length() == 1) {return result;}Deque stack = new LinkedList<>();stack.push(-1);for (int i =0;i 