一、括号生成【中等】

题目转变成“放n个左括号和n个右括号，放的过程中保证，左括号的数量始终大于等于右括号的数量，一共有多少种放法”

暴力搜索的思想（递归的手段）+回溯。

递归的第一件事是先分清用的是分治还是搜索，刚刚我们已经确定了，思想就是深度优先搜索。第二件事是画图：

然后定义递归子问题：generate(ans,left-1,right,temp+"(") 表示。。这里要注意，一定要先放左括号，不然在根节点就会全局退出。

然后根据递归出口写法的不同，有两种方式，我们先采用“先污染再治理”的方式，也就是递归出口都写在方法的最前面这种方式，也就是在第n+1轮的时候判断。

class Solution { public List<String> generateParenthesis(int n) { ArrayList<String> ans= new ArrayList(); generate(ans,n,n,""); return ans; } //left记录左括号剩下的，right记录右括号剩下的 public void generate(ArrayList<String> ans,int left, int right, String temp){ //1.找到一个答案，退出 if(left==0&&right==0){ ans.add(temp); return; } //2.剪枝 if(left<0) return; //3.剪枝 if(left>right) return; //用+“(”巧妙回溯 generate(ans,left-1,right,temp+"("); //用+“)”巧妙回溯 generate(ans,left,right-1,temp+")"); } }

递归出口的第二种方式，在进入第n+1次递归之前判断，也就是第n轮进行判断：

class Solution { public List<String> generateParenthesis(int n) { LinkedList<String> ans= new LinkedList(); generate(ans,n,n,""); return ans; } //left记录左括号剩下的，right记录右括号剩下的 public void generate(LinkedList<String> ans,int left, int right, String thisTurnResult){ //没有第n+1轮的递归出口 //1、第n轮判断：只剩一个右括号了，不用进入下次递归了，直接在这一轮结束 if(left==0 && right ==1){ ans.add(thisTurnResult+')'); return; } ///2、只能放左括号，需要回溯。这里通过传参的方式进行巧妙的回溯 if(left == right){ generate(ans,left-1,right,thisTurnResult+"("); //3、左括号、右括号都能放 }else{ //一定是左括号先用完 if(left>0){ generate(ans,left-1,right,thisTurnResult+"("); } generate(ans,left,right-1,thisTurnResult+")"); } } }

还有递归出口混着写的，第n+1轮也判断，第n轮也判断

class Solution { public List<String> generateParenthesis(int n) { LinkedList<String> ans= new LinkedList(); generate(ans,n,n,""); return ans; } //left记录左括号剩下的，right记录右括号剩下的 public void generate(LinkedList<String> ans,int left, int right, String thisTurnResult){ //===================第n+1轮退出================== if(left==0 && right ==0){ ans.add(thisTurnResult); return; } //===================第n轮退出================== //1、只能放左括号，需要回溯。这里通过传参的方式进行巧妙的回溯 if(left == right){ generate(ans,left-1,right,thisTurnResult+"("); //2、左括号、右括号都能放 }else{ //一定是左括号先用完 if(left>0){ generate(ans,left-1,right,thisTurnResult+"("); } generate(ans,left,right-1,thisTurnResult+")"); } } }

二、最长有效括号【困难】

思路1：先遍历一遍，把能“对对碰”消掉的都消掉。消不掉的把下标入栈。比如

" )( ( ) )(( )(( ) ( )"，栈里面剩的是[0, 5, 8]，然后把栈里剩的下标从后往前两两相减再-1，就能得到长度，需要注意的就是，要给[0, 5, 8]补充上首尾两端，首取-1，尾取s.length()，也就是[-1, 0, 5, 8, s.length()]。这样最大长度就从

s.length() - 8 -1

8 -5 -1

5 -0 -1

0 -（-1）-1

里面取最大的。

时间复杂度：O（n）+O（n）

空间复杂度：一个栈

class Solution { public int longestValidParentheses(String s) { //特殊情况 if(s.length()==0 || s.length()==1){ return 0; } //1、遍历一遍字符串，把能消掉的都消掉，消不掉的下标都留在stack里。时间复杂度O(n) Deque<Integer> stack = new LinkedList<>(); for(int i=0; i<s.length(); i++){ if(s.charAt(i)=='('){ stack.push(i); }else{ if(!stack.isEmpty()&&s.charAt(stack.peek())=='('){ stack.pop(); }else{ stack.push(i); } } } //2、遍历stack，时间复杂度O(n) //俩特殊情况 if(stack.size()==0) return s.length(); if(stack.size()==s.length()) return 0; int maxLength = 0; int lastIndex = s.length(); while(!stack.isEmpty()){ maxLength = java.lang.Integer.max(maxLength,lastIndex-stack.peek()-1); lastIndex = stack.peek(); stack.pop(); } maxLength=java.lang.Integer.max(maxLength,lastIndex-(-1)-1); return maxLength; } }

思路2：同样也是“对对碰消消乐”，但只遍历一次，遍历完这一次，顺便数出来哪一块是最大长度。如下图，我计算出下图中红色框框出的每个“对对碰小区间”的长度，通过比较得到最大值。

这样根本不行，因为你无法得知什么时候这个对对碰的小区间该结束了。根本原因在于只有遍历完一遍以后才知道哪个（左括号）没被消掉，你想一边遍历一遍判断，根本做不到。比如输入是“( ) ( ( )”，对于下标为2的那个左括号，你一直抱有后面有右括号和他配对的希望，但直到遍历完，才发现，并没有，然而你在遍历的过程当中是判断不出来的。

也就是下面这种写法，会在输入是“( ) ( ( )”的时候爆雷。

class Solution { public int longestValidParentheses(String s) { int length = s.length(); //特殊情况 if(length==0 ||length==1){ return 0; } //只遍历一遍字符串 int maxLength = 0; int i=0; Deque<Integer> stack = new LinkedList<>(); while(i<length){ int thisTurnMaxLength = 0; while(i<length){ //左括号 if(s.charAt(i)=='('){ stack.push(i); i++; //可以消掉的右括号，且没到最后 }else if(s.charAt(i)==')' && !stack.isEmpty() && s.charAt(stack.peek())=='(' && i!=length-1){ stack.pop(); thisTurnMaxLength = thisTurnMaxLength+2; i++; //可以消掉的右括号，到最后了 }else if(s.charAt(i)==')' && !stack.isEmpty() && s.charAt(stack.peek())=='('&& i==length-1){ stack.pop(); thisTurnMaxLength = thisTurnMaxLength+2; maxLength = java.lang.Integer.max(maxLength,thisTurnMaxLength); break; //无法消掉的右括号 }else{ maxLength = java.lang.Integer.max(maxLength,thisTurnMaxLength); break; } } i++; } return maxLength; } }

思路3：遍历一次，真的数不出来吗？动态规划可以做到！

或者问你，如果不用栈，你能做到吗？