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.

思路

棧的不是括號，而是括號的下標(biāo)

1. 遇到"("無條件入棧
2. 遇到“)”，如果stack不是空，彈出棧頂?shù)淖罄ㄌ?。比?code>((()
   • 彈出棧頂后，判斷stack是否為空，不為空表示有非法括號存在:
     1. 那么最后一個非法的左括號的下標(biāo)就是棧頂?shù)南聵?biāo)，所以當(dāng)前的合法括號組合的長度是i - stack.peek()
     2. 彈出棧頂后，如果stack為空，那么表示全部為合法括號對，此時合法括號組合的長度是 i - start
     3. start初始時為-1，但是當(dāng) ())(())這種情況出現(xiàn)時，第一隊括號已經(jīng)被消除了，第三個右括號出現(xiàn)時，那么start更新為他的下標(biāo)。

class Solution {
    public int longestValidParentheses(String s) {
        //入棧的不是括號，而是括號的下標(biāo)
        // 遇到"(" 無條件入棧
        // 遇到“）”，如果stack不是空，彈出棧頂?shù)淖罄ㄌ?。比?(()
            //1. 彈出棧頂后，判斷stack是否為空，不為空表示有非法括號存在，
            //那么最后一個非法的左括號的下標(biāo)就是棧頂?shù)南聵?biāo)，所以當(dāng)前的合法括號組合的長度是 i - stack.peek()
            //2. 彈出棧頂后，如果stack為空，那么表示全部為合法括號對，此時合法括號組合的長度是 i - start
                // start初始時為-1，但是當(dāng) ())(()) 這種情況出現(xiàn)時，第一隊括號已經(jīng)被消除了，第三個右括號出現(xiàn)時，那么start更新為他的下標(biāo)。
        int maxLen = 0;
        int start = -1;
        Stack<Integer> stack = new Stack<Integer>();
        
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                    if (!stack.isEmpty()) {
                        maxLen = Math.max(maxLen, i - stack.peek());
                    } else {
                        maxLen = Math.max(maxLen, i - start);
                    }
                } else {
                    start = i;
                }
            }
        }
        return maxLen;

    }
}