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;

		    }