最长有效括号

1.题目描述

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

示例 1: 输入: “(())” 输出: 4 解释: 最长有效括号子串为 “(())” 示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

2.解决方法

方法一：动态规划 设dp[i]代表前i个字符最大有效长度，是s[i]代表第i个符号 1.s[i]=’)’ && s[i-1]=’(’ 则dp[i]=dp[i-2]+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 方法二：贪心法 利用两个计数器 和 。首先，我们从左到右遍历字符串，对于遇到的每个 ，我们增加 计数器，对于遇到的每个，我们增加 计数器。每当 计数器与 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 计数器比 计数器大时，我们将 和 计数器同时变回 。这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这时候最长有效括号是求不出来的。解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算 方法三：栈 对于遇到的每个 ‘(’ ，我们将它的下标放入栈中 对于遇到的每个‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号： 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」 我们从前往后遍历字符串并更新答案即可。

需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 -1 的元素。

3.代码

//动态规划 public static int solution1(String s) { int maxlen=0; int dp[] = new int [s.length()]; for(int i=0;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; } maxlen=Math.max(maxlen, dp[i]); } } return maxlen; } //贪心法 public static int solution2(String s) { int left=0,right=0,maxlen=0; //从左到右 for(int i=0;i<s.length();i++) { if(s.charAt(i) == '(') left++; else right++; if(left == right) maxlen=Math.max(maxlen, 2*left); else if(right>left) right=left=0; } left=right=0; for(int i=s.length()-1;i>=0;i--) { if(s.charAt(i) == '(') left++; else right++; if(left == right) maxlen = Math.max(maxlen, 2*left); else if(left>right) right=left=0; } return maxlen; } //栈 public int solution3(String s) { int maxlen=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.isEmpty()) stack.push(i); else maxlen=Math.max(maxlen, i-stack.peek()); } } return maxlen; }