最长有效括号

BraumAce2024年10月9日约 915 字大约 3 分钟

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

思路一：栈模拟

用栈模拟一遍，将所有无法匹配的括号的位置全部置 $1$ 。

例如: "()(()" 的 mark 为 [0, 0, 1, 0, 0]

再例如: ")()((())"的 mark 为 [1, 0, 0, 1, 0, 0, 0, 0]

经过这样的处理后, 此题就变成了寻找最长的连续的 $0$ 的长度。

代码：

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        int n = s.length();
        int[] mark = new int[n];
        Arrays.fill(mark, 0);

        for (int i = 0; i < n; i++){
            if (s.charAt(i) == '(') st.push(i);
            else {
                // 多余的右括号是不需要的，标记
                if (st.isEmpty()) mark[i] = 1;
                else st.pop();
            }
        }

        // 未匹配的左括号是不需要的，标记
        while (!st.isEmpty()){
            mark[st.peek()] = 1;
            st.pop();
        }

        // 寻找标记与标记之间的最大长度
        int len = 0, ans = 0;
        for (int i = 0; i < n; i++){
            if (mark[i] == 1){
                len = 0;
                continue;
            }

            len++;

            ans = Math.max(ans, len);
        }

        return ans;
    }
}

思路二：动态规划

定义 DP 数组：dp[i] 表示以下标为 $i$ 的字符结尾的最长有效括号的长度
判断条件：
1. s[i] == '(' 时，s[i] 无法和其之前的元素组成有效的括号对，所以 dp[i] = 0
2. s[i] == ')' 时，需要看其前面对元素来判断是否有有效括号对。
  1. s[i − 1] == '('，即 s[i] 和 s[i − 1] 组成一对有效括号，有效括号长度新增长度 $2$ ，i 位置的最长有效括号长度为 其之前2个位置的最长括号长度加上当前位置新增的 $2$ ，我们无需知道 i − 2 位置对字符是否可以组成有效括号对。
    那么有：dp[i] = dp[i − 2] + 2
  2. s[i − 1] == ')'，这种情况下，如果前面有和 s[i] 组成有效括号对的字符，即形如 ((....))，那就要求 s[i − 1] 位置必然是有效的括号对，否则 s[i] 无法和前面对字符组成有效括号对。
    这时，我们只需要找到和 s[i] 配对的位置，并判断其是否是 ( 即可。和其配对的位置为：i − dp[i − 1] − 1。
    如果：s[i − dp[i − 1] −1] == '()'：有效括号长度新增长度 $2$ ，i 位置的最长有效括号长度为 i - 1 位置的最长括号长度加上当前位置新增的 2，那么有：dp[i] = dp[i − 1] + 2
    值得注意的是，i − dp[i − 1] − 1 和 i 组成了有效括号对，这将是一段独立的有效括号序列，如果之前的子序列是形如 (...) 这种序列，那么当前位置的最长有效括号长度还需要加上这一段。
    所以：dp[i] = dp[i − 1] + dp[i − dp[i − 1] − 2] + 2
综上可得：
1. 当 s[i] == '(' 时，dp[i] 必然等于 $0$ ，因为不可能组成有效的括号；
2. 当 s[i] == ')' 时：
  1. 若 s[i - 1] == '('，则 dp[i] = dp[i - 2] + 2；
  2. 若 s[i - 1] == ')' 且 s[i - dp[i - 1] - 1] == '('，则 dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
3. 每次循环取最大的 dp[i] 即可

代码：

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (s == null || n == 0) return 0;

        int[] dp = new int[n];
        int ans = 0;

        for (int i = 0; i < n; i++){
            if (i > 0 && s.charAt(i) == ')'){
                if (s.charAt(i - 1) == '('){
                    if (i - 2 >= 0){
                        dp[i] = dp[i - 2] + 2;
                    } else {
                        dp[i] = 2;
                    }
                } else if (s.charAt(i - 1) == ')' &&
                            i - dp[i - 1] - 1 >= 0 &&
                            s.charAt(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 = Math.max(ans, dp[i]);
        }

        return ans;
    }
}

最长有效括号

最长有效括号

题意

思路一：栈模拟

思路二：动态规划