32. 最长有效括号动态规划

32. 最长有效括号

难度：困难 2020/7/4每日一题打卡√ 题目描述 解题思路

1、动态规划

困难题果然有困难的道理，这道题一看就知道是动态规划，可是一写就不会 dp[i]代表以i结尾的连续有效子串的长度，只有当是s[i]是右括号）的时候，才有意义 举几个简单的例子： 比如（），第一个是左括号肯定形不成子串，遇到右括号，那就等于2 此时的dp数组就是0 2 如果是（）（）（）这种连续的，每次匹配一个括号对，dp[i] = dp[i-2]+2 dp数组是0 2 0 4 0 6

也有可能是（（（）））这种嵌套的情形，到最中间那个括号对，dp数组是 0 0 0 2 0 0，对于后面的右括号，就往前去寻找有没有匹配的左括号，找的下标是i - dp[i-1]-1，对应的是当前右括号下标减去中间匹配的括号个数的前一个，就刚好是左括号，如果匹配，那dp[i] = dp[i-1] + 2，就是在前一个匹配的数字基础上，再加上2 最后的dp数组是0 0 0 2 4 6

但是这样也是有问题的，比如（）（）（（（）））这种情况，按照上面的方法，最后得到的dp数组是这样0 2 0 4 0 0 0 2 4 6，最后得到的结果是6. 但是应该是10，问题就出在，最后一个右括号匹配上的时候，对应的左括号左边已经有了四个匹配的括号，没有加上这个4 所以对于嵌套括号的匹配，除了加上2，还要加上匹配的左括号左边对应的dp值。要注意下标

public int longestValidParentheses(String s) { char[] str = s.toCharArray(); int n = str.length; int[] dp = new int[n+1]; //dp[i]表示第i个位置结尾的最大长度 int max = 0; for (int i = 1; i < n; i++) { if(str[i] == ')') { if(str[i-1] == '(') { //如果和前面的组合成() dp[i+1] = dp[i-1] + 2; }else { //针对((()))这种嵌套的情况 if(i-dp[i]-1 >= 0 && str[i-dp[i]-1] == '(') { dp[i+1] = dp[i] + 2 + dp[i-dp[i]-1]; } } max = Math.max(max, dp[i+1]); } //System.out.print(str[i]+" "+dp[i+1]); } return max; }

2、用栈模拟

先在栈里面放一个初始元素-1防止越界，栈顶元素表示匹配开始的位置 关键难理解的地方就是这样混合的情况（）（（（））） 遇到左括号入栈，栈里面是-1 0 遇到右括号，出栈一个左括号，就是-1，此时栈还不是空，计算匹配区间长度1-（-1） = 2 然后入栈 -1 2 3 4 遇到一个右括号，出栈4，长度5-3=2 同理，出栈到最后一个右括号的时候栈里面只有-1，长度就是5+1=6

public static int longestValidParentheses(String s) { char[] str = s.toCharArray(); int n = str.length; int max = 0; Stack<Integer> stack = new Stack<>(); stack.push(-1); //防止越界 for (int i = 0; i < n; i++) { if(str[i] == '(') { //左括号入栈 stack.push(i); } if(str[i] == ')') { //右括号出栈，计算匹配值 stack.pop(); if(stack.isEmpty()) { //如果栈为空，重新开始记录 stack.push(i); }else { max = Math.max(max, i-stack.peek()); } } } return max; }