32. Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

一個(gè)只有“（”與“）”的字符串，找到最長(zhǎng)的成對(duì)的子串。

算法3（無重復(fù)子串）、算法5（回文子串）都是找子串的，對(duì)于字符串的算法，都離不開遍歷。
思路一，暴力遍歷。在算法20中，也是求符號(hào)是否成對(duì)，其中一個(gè)思路是用一個(gè)stack記錄遍歷過的符號(hào)，利用stack先進(jìn)后出的特性，與后面的符號(hào)進(jìn)行配對(duì)。在這道題中也適用，但是這道題求最長(zhǎng)的一個(gè)，所以暴力遍歷出所有的子串，然后分別去判斷是否合法，記錄最長(zhǎng)的長(zhǎng)度?？臻g復(fù)雜度最壞情況下，需要裝n-1個(gè)符號(hào)，即n-1個(gè)符號(hào)都相同，那么空間復(fù)雜度為O(n)。時(shí)間復(fù)雜度，遍歷出所有子串為O(n^{2)，判斷是否合法再乘以n，故為O(n}3)。

思路二：
也是使用stack去判斷是否配對(duì)，但是沒必要遍歷出全部子串。題目要求一個(gè)配對(duì)返回長(zhǎng)度2，我們先把-1加入到棧中，遍歷字符串，如果是左括號(hào)，把位置i加入到stack中。如果遇到右括號(hào)，stack出棧一位，如果此時(shí)stack為空，表示不合法；使用i - stack.pop() ，就是當(dāng)前配對(duì)的長(zhǎng)度。為了計(jì)算后續(xù)是否配對(duì)，需要再將當(dāng)前位置i入棧。這個(gè)算法的話，只需要遍歷一次，故時(shí)間復(fù)雜度為O(n)。最壞的空間復(fù)雜度為O(n)，原因與思路一相同。

以下為代碼：

public int longestValidParentheses(String s) {
    int maxLen = 0;
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(-1);

    for (int i = 0; i < s.length(); i++) {
        if('(' == s.charAt(i)) {
            stack.push(i);
        } else {
            stack.pop();
            if(stack.isEmpty()) {// 這種情況肯定不合法
                stack.push(i);
            } else {// 配上對(duì)了
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }

    return maxLen;
}