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.

一刷
題解：

• 使用類(lèi)似valid parentheses的方法劣摇。
  1. 維護(hù)一個(gè)depth信柿，一個(gè)count。
  2. 從左向右遍歷時(shí)并且當(dāng)char == '('時(shí)咏删，depth++，否則char = ')'销斟，depth--岖寞，這時(shí)候我們count++，因?yàn)檎业搅艘粚?duì)valid parenthese
  3. 當(dāng)depth == 0的時(shí)候宠漩，左右括號(hào)平衡举反，可以嘗試更新max， max = Math.max(max, count * 2)
  4. 接下來(lái)判斷depth是否小于0扒吁，小于0的話depth = 0, count = 0火鼻，我們從頭開(kāi)始計(jì)算。
  5. 左右各自遍歷一遍雕崩。從右向左遍歷是為了計(jì)算類(lèi)似于"()(()()"這種情況魁索，這時(shí)depth always > 0，沒(méi)辦法得到max = 4的結(jié)論盼铁。
• 一種是一維DP粗蔚，分好幾種情況，畫(huà)一個(gè)decision tree會(huì)比較清楚邏輯饶火。
  1. 維護(hù)一個(gè)數(shù)組max[], 其中max[i]代表以s.charAt(i)結(jié)尾的longest valid parentheses的長(zhǎng)度鹏控。我們考慮接下來(lái)集中情況。
  2. max[0] = 0肤寝，因?yàn)榇藭r(shí)不能組成"()"当辐。所以我們可以直接從 i = 1開(kāi)始遍歷
  3. 當(dāng)前字符是'('， max[i] = 0鲤看，因?yàn)関alid parentheses不能以'('結(jié)尾
     否則缘揪，當(dāng)前字符等于')'，這時(shí)候繼續(xù)判斷幾種情況
     1. s.charAt(i - 1) = '('，正好可以組成一對(duì)括號(hào)寺晌。
        1. 當(dāng) i - 2 >= 0世吨，max[i] = max[i - 2] + 2
        2. 當(dāng) i - 2 < 0， max[i] = 2
     2. 否則s.charAt(i - 1) = ')'呻征，此時(shí)我們也是繼續(xù)進(jìn)行判斷
        1. 此時(shí)我們要求出i關(guān)于max[i - 1]對(duì)稱(chēng)的字符耘婚，就是 i - max[i - 1] - 1
           假如i - max[i - 1] - 1 >= 0，并且 s.charAt(i - max[i - 1] - 1) == '('
           此時(shí)表示從i - max[i - 1] - 1到i這一段都合理陆赋，所以這一部分等于max[i - 1] + 2, 我們要繼續(xù)判斷 i - max[i - 1] - 2
           當(dāng)i - max[i - 1] - 2 >= 0沐祷， 則 max[i] = max[i - 1] + 2 + max[i - max[i - 1] - 2]
           否則max[i] = max[i - 1] + 2
           否則max[i] = 0，我們不改變什么
  4. 在開(kāi)頭維護(hù)一個(gè)res = 0攒岛， 每次計(jì)算完max[i]之后嘗試更新這個(gè)res赖临，最后返回的也是這個(gè)res.
  5. 其實(shí)還可以繼續(xù)簡(jiǎn)化，留給三刷了

第一種方法：

public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length()<=1) return 0;
        int count = 0, max=0, depth = 0;
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(c == '(') depth++;
            else{
                depth--;
                count++;
                if(depth == 0) max = Math.max(max, count*2);
                if(depth<0){
                    depth = 0;
                    count = 0;
                }
            }
        }
        
         depth = 0;
         count = 0;
        for(int i=s.length()-1; i>=0; i--){
            char c = s.charAt(i);
            if(c == ')') depth++;
            else{
                depth--;
                count++;
                if(depth == 0) max = Math.max(max, count*2);
                if(depth<0){
                    depth = 0;
                    count = 0;
                }
            }
        }
        
        return max;
    }
}

二刷:
accumulatedLen來(lái)積攢matchedLen
Stack

public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int maxLen = 0;
        int accumulatedLen = 0;
        
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '(') stack.push(i);
            else{
                if(stack.isEmpty()) accumulatedLen = 0;//())()(), )的數(shù)目比(多
                else{
                    int matchedLen = i - stack.pop() + 1;
                    if(stack.isEmpty()){
                        accumulatedLen += matchedLen;
                        matchedLen = accumulatedLen;
                    }
                    else{//"(()()" ,用i - stack.peek()來(lái)得到valid parenthesis個(gè)數(shù)
                       matchedLen = i - stack.peek(); 
                    }
                    maxLen = Math.max(maxLen, matchedLen);
                }
            }
        }
        return maxLen;
    }
}