LeetCode-32. 最长有效括号

题目来源

32. 最长有效括号

题目详情

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

示例 1：

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

示例 2：

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

示例 3：

输入： s = ""
输出： 0

提示：

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

题解分析

解法一：动态规划

1. 本题要求解最长有效括号子串长度，碰到子串，最长等描述词语就能想到应该使用动态规划来求解。
2. 本题的难点就在于状态转移方程的定义，这部分是比较难分析的，因为这里涉及到两种符号：即左括号和右括号。而左右括号之间会相互影响。
3. 我们可以定义dp[i]表示以i结尾的最长有效符号子串的长度。接下来分析可能出现的情况。
   • 首先需要说明的是，当前符号为"("时，其实不用考虑，因为这种情况一定不能构造出比前面的子串更长的有效括号子串。所以，我们只考虑当前符号为")"的情况。
   • 第一种情况是，当前符号的前一个符号为"("。也就是说，字符串的形式为："...()"。这里很容易得到：\(dp[i] = dp[i-2] + 2\);
   • 第二种情况是：当前符号的前一个符号为")"。也就是说，字符串的形式为："...((...))"。这里需要判断，当第\(i-dp[i-1]-1\)个字符为"("时，可以得到状态转移方程：\(dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2\)。
4. 综上，我们可以定义一个最大值记录量max，用来记录最长有效括号子串的长度。

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];// dp[i]表示以i结尾的子串的最长有效括号子串的长度
        int max = 0;
        for(int i=1; i= 2 ? dp[i-2] : 0) + 2;
                }else if(i - dp[i-1] >= 1 && s.charAt(i-dp[i-1]-1) == '('){
                    // "...((...))"的情况
                    dp[i] = dp[i-1] + 2 + ((i - dp[i-1] >= 2) ? dp[i-dp[i-1]-2] : 0);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;// 注意，这里不能返回dp[n-1]，因为这里不能保证以n-1结尾的符号一定有满足连续的最长有效括号子串
    }
}

解法二：栈

1. 使用栈的解法比较复杂，也比较难以理解，这里考了一些思维。
2. 通过栈可以维护【字符串中最后一个未匹配的右括号的下标位置】。
3. 具体的可以参考官方题解。

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int max = 0;
        Deque sta = new LinkedList<>();// 栈用来存放字符串中最后的没有被匹配的右括号的位置
        sta.push(-1);// 为了保持统一，放入-1表示最后一个未被匹配的右括号位置为-1
        for(int i=0; i