題目描述

給你一個只包含 '(' 和 ')' 的字符串，找出最長有效（格式正確且連續(xù)）括號子串的長度。

示例 1：

輸入：s = "(()"
輸出：2
解釋：最長有效括號子串是 "()"
示例 2：

輸入：s = ")()())"
輸出：4
解釋：最長有效括號子串是 "()()"
示例 3：

輸入：s = ""
輸出：0

提示：

0 <= s.length <= 3 * 104
s[i] 為 '(' 或 ')'

題解

始終保持棧底元素為當(dāng)前已經(jīng)遍歷過的元素中最后一個沒有被匹配的右括號的下標(biāo)

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        Stack<Integer> st = new Stack<>();
        st.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.isEmpty()) {
                    st.push(i);
                } else {
                    max = Math.max(max, i - st.peek());
                }
            }
        }
        return max;
    }
}