leetcode32 Longest Valid Parentheses 最长括号组的长度

摘要：题目要求原题地址一个括号序列，求出其中成对括号的最大长度思路一使用堆栈这题可以参考我的另一篇博客这篇博客讲解了如何用堆栈判断括号序列是否可以成对。我们可以将堆栈的思路延续到这里。在这里需要先遍历一遍字符串，再遍历一下非空的堆栈。

原题地址：https://leetcode.com/problems...

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.

一个括号序列，求出其中成对括号的最大长度

这题可以参考我的另一篇博客,这篇博客讲解了如何用堆栈判断括号序列是否可以成对。我们可以将堆栈的思路延续到这里。每当遇到一个左括号或者是无法成对的右括号，就将它压入栈中，可以成对的括号则从栈中压出。这样栈中剩下的就是无法成对的括号的下标。这时我们可以判断这些下标间的距离来获得最大的成对括号长度。在这里需要先遍历一遍字符串，再遍历一下非空的堆栈。

    public int longestValidParentheses(String s) {
        Stack parenthesesStack = new Stack();
        for(int i = 0 ; i < s.length() ; i++){
            char symbol = s.charAt(i);
            if(symbol==")"){
                //在这里左右括号可以成对，则出栈
                if(!parenthesesStack.isEmpty() && parenthesesStack.peek().symbol=="("){
                    parenthesesStack.pop();
                    continue;
                }
            }
            //其他情况都压入栈中
            parenthesesStack.push(new Parenthese(symbol, i));
        }
        int maxLength = 0;
        int nextIndex = s.length();
        while(!parenthesesStack.isEmpty()){
            int curIndex = parenthesesStack.pop().index;
            maxLength = (nextIndex-curIndex-1)>maxLength ? nextIndex-curIndex-1 : maxLength;
            nextIndex = curIndex;
        }
        return Math.max(nextIndex, maxLength);
    }
    
    public class Parenthese{
        char symbol;
        int index;
        public Parenthese(char symbol, int index){
            this.symbol = symbol;
            this.index = index;
        }    
    }

在这里可以优化，因为使用数据结构不是必要的。我们可以直接压入栈中下标，再从字符串中获得该下标对应的字符

    public int longestValidParentheses_noDataStructure(String s) {
        Stack parenthesesStack = new Stack();
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i)==")"){
                if(!parenthesesStack.isEmpty() && s.charAt(parenthesesStack.peek())=="("){
                    parenthesesStack.pop();
                    continue;
                }
            }
            parenthesesStack.push(i);
        }
        int maxLength = 0;
        int nextIndex = s.length();
        while(!parenthesesStack.isEmpty()){
            int curIndex = parenthesesStack.pop();
            int curLength = nextIndex-curIndex-1;
            maxLength = curLength>maxLength ? curLength : maxLength;
            nextIndex = curIndex;
        }
        return Math.max(nextIndex, maxLength);
    }

dynamic programming 的真 奥义其实在于假设已知之前所有的结果，结合之前的结果穷尽每一种当前值可能的情况
在这道题目中，我们假设已经知道长度为n-1字符串中，到每一个下标为止的的最大的括号组长度，这些值被存储在和字符串长度等长的int数组s中，其中s的下标代表字符串的下标，s的值代表到这个字符串下标为止最长括号组长度。
那么当前第n个符号主要有以下三种情况:

当前值为‘(’，那么无论前面情况如何，当前一定是无法形成括号的，所以最大长度为0

当前值为‘)’，前一个值为‘(‘, 那么最大长度为s[n-2](如果存在的话）+ 2

当前值为‘)’，前一个值也是")"，如果在i-s[i-1]-1的位置上是一个’(‘，那么最大长度为s[i-1]+2+s[i-s[i-1]-2]，具体情况可以参考()(())当n=5时,否则仍旧为0

代码实现如下

    public int longestValidParentheses_dynamicProgramming(String s) {
        int[] maxCount = new int[s.length()];
        int maxLength = 0;
        for(int i = 1 ; i=2? maxCount[i-2]+2 : 2);
                    maxLength = Math.max(maxCount[i], maxLength);
                }else{
                    if(i-maxCount[i-1]-1>=0 && s.charAt(i-maxCount[i-1]-1)=="("){
                        maxCount[i] = maxCount[i-1]+2 + ((i-maxCount[i-1]-2 >= 0)?maxCount[i-maxCount[i-1]-2]:0);;
                        maxLength = Math.max(maxCount[i], maxLength);
                    }
                }
            }
        }
        return maxLength;        
    }

简化后的代码如下：

    public int longestValidParentheses_dynamicProgrammingConcise(String s) {
        int[] maxCount = new int[s.length()];
        int maxLength = 0;
        for(int i = 1 ; i=0 && s.charAt(i-maxCount[i-1]-1)=="("){
                maxCount[i] = maxCount[i-1] + 2 + ((i-maxCount[i-1]-2>=0) ? maxCount[i-maxCount[i-1]-2] : 0);
                maxLength = Math.max(maxCount[i], maxLength);
                
            }
        }
        return maxLength;        
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~