摘要：題目要求原題地址一個括號序列，求出其中成對括號的最大長度思路一使用堆棧這題可以參考我的另一篇博客這篇博客講解了如何用堆棧判斷括號序列是否可以成對。我們可以將堆棧的思路延續(xù)到這里。在這里需要先遍歷一遍字符串，再遍歷一下非空的堆棧。

原題地址：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.

一個括號序列，求出其中成對括號的最大長度

這題可以參考我的另一篇博客,這篇博客講解了如何用堆棧判斷括號序列是否可以成對。我們可以將堆棧的思路延續(xù)到這里。每當遇到一個左括號或者是無法成對的右括號，就將它壓入棧中，可以成對的括號則從棧中壓出。這樣棧中剩下的就是無法成對的括號的下標。這時我們可以判斷這些下標間的距離來獲得最大的成對括號長度。在這里需要先遍歷一遍字符串，再遍歷一下非空的堆棧。

    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;
        }    
    }

在這里可以優(yōu)化，因為使用數據結構不是必要的。我們可以直接壓入棧中下標，再從字符串中獲得該下標對應的字符

    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;        
    }

想要了解更多開發(fā)技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~