链接： https://leetcode.com/problems/longest-valid-parentheses/
【描述】
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
【中文描述】
给定一个String， 它只含有"("和")"两种字符，要求求出其中最长的合法组合。例子上面有。
————————————————————————————————————————————————————————————
【初始思路】
首先，确定一下，要用stack，这个是毋庸置疑的。不用stack不是不可以，但是会很累。
其次，用递归是肯定可以的。但是，递归太慢，太耗空间。
那么，用什么办法解决？
仔细研究了一下，所谓合法（）组合，是有一个绝对正确的性质的：
在合法的串里， 每个 ')' 都能在之前找到一个 '(' 与之对应！
我们的解法就依据这句话来做了。怎么弄呢？
既然上面的说了，前提是在合法串里。那我们就想办法把合法串找出来嘛！大家肯定要吐槽了，你都找出来了，那长度还不好算？其实仔细想想确实不好算，因为我们这里实际上只是用stack把string从左往右撸了一遍。当前字符如果属于合法串，就给它一个标记。但是很显然，仅凭这些标记是无法确定具体串是什么样子，起止点在哪的。
等有了标记后，我们就可以根据上面的性质来算长度了。
好，上面是大致思路，我们来看看具体怎么给标记。
首先，创建一个和string等长的的int[]. 用来记录每一位的标记。
然后，遍历一遍string。那么，对于每个字符，有2种情况：
（1）当遇到'('的时候，入栈，标记给0。因为很显然，仅仅有一个'('我怎么知道你后面会不会有')'来配对呢， 所以我先给你一个0吧。
（2）当遇到')'的时候，应该从栈里出栈一个元素。此时还有2种情况：
(2.1) 栈已经是空的了。那显然，这个')'在前面找不到和它配对的。直接给0；
(2.2) 栈里还有元素，出栈成功。 这个时候， 说明这个')'在前面肯定有一个和它能够配对的。位置我可能不知道在哪，但是是肯定存在的。好，我们就给这个')'一个2作为标记。用来表示，这个')'属于一个配对组，并且一个配对组肯定是2个字符嘛。
此外，还要考虑边界情况。字符串第一个元素特殊对待一下，如果是'('自然是标记0，如果是')'，那也给标记为0（显然不能配对嘛）。
好，到了这里，我们势必能得到一个int数组，里面只有2种数字： 0 和 2。
接下来怎么找呢？
根据前面那条重要的性质，在合法串里，每个2在前面必然会有一个0和它对应。那么，我们从后往前遍历一遍，给2一个计数器嘛，遇到2就加1，遇到0就减1嘛。而当遇到0且此时计数器已经为0的时候，说明遇到了不能配对的'('或')'，那么此时合法串肯定被这个"害群之马"打断了，我们之前的配对就只能告一段落。把之前的这个合法串的长度更新到max里，然后2的计数器置为0，接着遍历。直到结束。
遍历结束后，我们实际上就肯定能够得到最大的合法串的配对数了嘛，然后return max * 2不就好了么。
【Show me the Code!!!】
1 public static int longestValidParentheses(String s) { 2 if (s == null || s.length() == 0 || s.length() == 1) { 3 return 0; 4 } 5 int n = s.length(); 6 int[] d = new int[n]; 7 8 Stack<Character> stack = new Stack<Character>(); 9 10 if (s.charAt(0) == '(') { 11 stack.push(s.charAt(0)); 12 d[0] = 0; 13 } else { 14 d[0] = 0; 15 } 16 for (int i = 1; i < n; i++) { 17 if (s.charAt(i) == '(') { 18 stack.push(s.charAt(i)); 19 //最后一位是'('的特殊情况 20 d[i] = 0; 21 } else { 22 if (stack.size() == 0 ) { 23 //说明当前不匹配 24 //当前置为0 25 d[i] = 0; 26 } else { 27 stack.pop(); 28 d[i] = 2; 29 } 30 } 31 } 32 33 /** 34 * 整理d[], 现在d[]里只有0和2 35 * 从后往前, 对2计数, 遇到2就加1, 遇到0就-1;再维护一个总2的个数.遇到2就加1 36 * 当计数<0的时候,2计数清0, 比较max和当前2总数. 需要时更新max 37 * 当循环彻底结束后, return 2的总个数 * 2 即为所求 38 */ 39 int twoCount = 0; 40 int totalTwo = 0; 41 int max = 0; 42 int i = d.length - 1; 43 while ( i >= 0) { 44 if (d[i] == 0) { 45 twoCount--; 46 if (twoCount < 0 || i == 0) { 47 twoCount = 0; 48 if (totalTwo > max) { 49 max = totalTwo; 50 } 51 totalTwo = 0; 52 } 53 i--; 54 } else { 55 twoCount++; 56 totalTwo++; 57 i--; 58 } 59 } 60 return max * 2; 61 }
虽然是AC了，而且也是O(n)的时间复杂度，但是总觉得这个方法挺笨的，而且其实遍历了两遍，速度肯定慢。能否只遍历一遍解决呢？
回想一下，上面之所以遍历了两遍，是因为在第一次遍历的时候我们无法计算长度，因为我们存的仅仅只是字符。那么换个思路，我们能否在stack里存位置。位置和位置之间肯定是能通过相减算出位置差的，位置差其实不就是长度么？
这个时候，出入栈规则和上面就需要有一定差异了，我们来分析一下。
'('的位置入栈没有问题，而遇到')'的时候，有2种可能性：
（1）栈顶是一个'('，那不用说了，'('出栈，然后用当前位置 i 减去'('出栈后的栈顶位置，就是当前长度;
（2）栈顶一个')'，那么当前的这个')'怎么处理？跳过？我们用下面例子来看一下：
( ) ) ( ( ) )
0 1 2 3 4 5 6
首先遇到0入栈，再遇到1，0出栈，此时栈为空，没有栈顶元素了，所以我们首先在栈里放一个-1. 为什么放-1而不放别的值呢。其实是为了方便计算从最开始位置到当前位置的总长度。此时，相当于0出栈后，栈里还有一个-1. 然后1-(-1)=2， 当前最长长度是2，没问题。
接下来，遇到2位置，是个')'，我们先不管它，直接continue。接下来，3入栈，遇到4，也入栈。
然后，遇到5，4出栈，5-3 = 2。最大长度是2，也没问题。接下来遇到6，3出栈，此时栈里只有-1了， 然后6-（-1） = 7 ，最大长度更新为7，显然不对。
出错的原因在于，按照道理来讲，其实在2的位置是有一个')'存在，而我们没有加入栈中去。这时，如果遇到上面的情况，那么4和3分别出栈后，直接暴露了栈底给程序。相当于从后往前全算进去了。这显然是不对的。换句话说，有')'在的时候，我们可以帮助程序判断从哪里应该截断重新计算长度。所以，遇到')'而前一个位置不是'('的时候，或者当前栈顶就是-1的时候，')'也应该入栈。
这样的话，从前遍历到后，一遍就可以算出最大长度来，我们来看看代码：
【Show me the Code!!!】
1 public int longestValidParentheses(String s) { 2 Stack<Integer> st = new Stack<Integer>(); 3 st.push(-1); 4 int len = 0; 5 for(int i=0;i<s.length();i++){ 6 if(s.charAt(i)==')'&&st.peek()!=-1&&s.charAt(st.peek())=='('){ 7 st.pop(); 8 len = Math.max(len,i-st.peek()); 9 } 10 else st.push(i); 11 } 12 return len; 13 }
这个代码就干净、简洁了很多！而且速度上来讲，对于短s的情况下，会比上面的算法快一倍！
【DP】
DP解法还在消化中，稍后更新。