leetcode **32. 最长有效括号（2020.7.4）

【题目】**32. 最长有效括号

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

【解题思路1】暴力法

超时 取<=字符串长度的最小偶数区间遍历字符串，如果该长度有有小括号那这就是最长长度，如果没有的话区间长度-2继续遍历判断

class Solution { public int longestValidParentheses(String s) { int l=s.length()/2*2; for(int i=l;i>=2;i-=2){ for(int j=0;j<=s.length()-i;j++){ String s1=s.substring(j,j+i); if(youxiaokuohao(s1)){return i;} } } return 0; } public boolean youxiaokuohao(String s1){ Stack<Integer> stack=new Stack<>(); for(int i=0;i<s1.length();i++){ if(s1.charAt(i)=='('){ stack.push(i); } else{ if(stack.isEmpty()){return false;} else{stack.pop();} } } return stack.isEmpty(); } }

【解题思路2】动态规划

dp数组的状态：dp[i]表示以 i 位置结尾的最长有效子字符串的长度 边界条件：因为有效括号一定是成对出现的，所以作为结尾的括号一定是右括号，所以左括号对应的dp[]值一定是0 状态转移方程：dp[i] = 2 + dp[i-1] + dp[ i - dp[i-1] - 2 ]

判断 i - dp[i-1] - 1 是否是左括号，如果是则基础长度为2加上内部包含的最长有效括号长度是 dp[i-1]加上外部包含的最长有效括号是dp[ i - dp[i-1] - 2 ]

注意上面的 dp[-1]，是为了表示 0 位置前面的元素

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; } }

【解题思路3】栈

遇到左括号入栈，遇到右括号先出栈然后计算长度 先入栈一个-1，作为最长子串的第一个分割点 这边遇到了2位置，-1匹配出栈，栈空，2入栈，作为新的分割点

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; } }

【解题思路4】正向逆向结合

记录左括号个数left、右括号个数right，还有最大子串长度maxlength 从左向右遍历：

当 left = right，更新maxlength = left * 2当 right > left，重置 left = 0, right = 0，说明这个右括号是分割点 如果2位置是左括号，从左往右遍历到最后，maxlength没有得到更新，所以还需要从右往左遍历一遍当 left = right，更新maxlength = left * 2当 left > right，重置 left = 0, right = 0，说明这个左括号是分割点 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; } }