32.最长有效括号

下标栈+记忆化

有效括号组先左后右的特性，故不存在栈中存放右括号的情况 维护一个栈，记录栈中左括号的下标；维护一个DP数组，记录当前位置是否达成一个有效括号组以及该括号组的长度 遍历字符，对于一个字符：

• (
  • 不可能构成包含当前位置的有效括号组，入栈、dp置为 -1
• )
  • 当前栈为空，直接跳过
  • 栈不为空，那么该括号组的长度为 当前下标 - 栈顶下标 + 1
    • 检查 栈顶下标 + 1 的 dp 位置，若该值不为 -1，表示当前括号组可以与上一个括号组合并
    • 若栈顶下标 + 1 的 dp 值为 1，则无法合并

show code

class Solution {
    public int longestValidParentheses(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int ans = 0;
        // 左括号的下标
        LinkedList<Integer> stack = new LinkedList<>();
        int[] dp = new int[n]; // 每个下标的最大括号组长度
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty()) {
                if (arr[i] == '(') {
                    stack.addLast(i);
                    dp[i] = -1; // 当前未能构成有效组
                }
                continue;
            }
            if (arr[i] == ')') {
                int index = stack.removeLast();
                // 计算当前有效的括号组长度
                int currLen = i - index + 1;

                // 是否能与前一括号组合并
                if (index > 0 && dp[index - 1] != -1) {
                    dp[i] = currLen + dp[index - 1];
                } else {
                    dp[i] = currLen;
                }
                ans = Math.max(dp[i], ans);
            } else {
                stack.addLast(i);
                dp[i] = -1; // 当前未能构成有效组
            }
        } 
        return ans;
    }
}