最长子数组乘积

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号

子串

的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

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

解题思路

方法一：动态规划

我们用 dp[i] 表示以 i 结尾的最长有效括号；

• 当 s[i] 为 (，dp[i] 必然等于 0，因为不可能组成有效的括号；

• 那么 当s[i] 为 )

  • 当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2；
  • 当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；

时间复杂度：O(n)

如下图所示

注意要判断 i - dp[i-1] - 1 和 i - dp[i - 1] - 2必须>=0

class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        if(len == 0 || len == 1) return 0;
        char[] chars = s.toCharArray();
        int[] dp = new int[len];
        int ans = 0;
        if(chars[0] == '(' && chars[1] == ')'){
            dp[1] = 2;
            ans = 2;
        }
        for(int i = 2; i < len; i++){
            if(chars[i] == '('){
                dp[i] = 0;
            }else if(chars[i] == ')'){
                if(chars[i-1] == '('){
                    dp[i] = dp[i-2] + 2;
                }else if(chars[i-1] == ')' && i - dp[i-1] - 1 >= 0 && chars[i - dp[i-1] - 1] == '('){
                    if(i - dp[i-1] - 2 >= 0){
                        dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2];
                    }else{
                        dp[i] = dp[i-1] + 2;
                    }
                }
            }
            ans = dp[i] > ans ? dp[i] : ans;

        }
        return ans;
    }
}

方法二：栈

用栈保存最后一个未匹配元素的下标，

• 如果找到左括号则入栈，为寻找对应右括号做铺垫
• 如果是右括号则出栈
  • 如果出栈后栈为空，则将右括号下标入栈（该右括号未能匹配），表示右括号下标之前都是未匹配的，比如第一个元素是右括号，则会先将-1出栈，再将0入栈，则0下标之前都是为匹配的
  • 如果出栈后不为空，说明右括号抵消了左括号，取当前右括号下标和栈顶元素差值（右括号为结尾的最长有效括号的长度）

初始化需要向栈中入栈-1，方便对i - st.peek()进行计算

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