🌕🌕32. 最长有效括号

难度: 🌕🌕

问题描述

---

解法 1 - 栈

class Solution {
    public int longestValidParentheses(String s) {
        // 思路：
        // 借助 栈 - 栈中存放的下标
        int len = s.length();
        LinkedList<Integer> stack = new LinkedList<>();
        int res = 0;
        int pre = 0;
        for(int i = 0; i < len; i ++) {
            char cur = s.charAt(i);
            if(cur == '(') {
                stack.push(i);
            } else {
                // cur == ')'
                // 判断栈是否为空，若非空，则栈中存放的肯定是 '('，可以与之配对
                if(stack.isEmpty()) {
                    pre = i + 1; // 下次计算的左边界为 i
                } else {
                    stack.pop();
                    if(stack.isEmpty()) {
                        res = Math.max(res, i - pre + 1);
                    } else {
                        res = Math.max(res, i - stack.peek());
                    }
                }
            }
        }
        return res;
    }
}

---

输出 1

---

解法 2 - dp

class Solution {
    public int longestValidParentheses(String s) {
        // 思路：
        // dp[i] -- 以 i 结尾的括号子串的长度
        int len = s.length();
        int[] dp = new int[len];
        int res = 0;
        for(int i = 1; i < len; i ++) {
            if(s.charAt(i) == ')') {
                // 只有遇到 ')' 才进行计算
                // 取决于 ')' 前面是 '(' 还是 ')'
                if(s.charAt(i - 1) == '(') {
                    // ...() 的格式
                    if(i - 2 >= 0) {
                        dp[i] = dp[i - 2] + 2;
                        res = Math.max(res, dp[i]);
                    } else {
                        dp[i] = 2;
                        res = Math.max(res, dp[i]);
                    }
                } else {
                    // ...)) 的格式
                    // ')' 前面的 ')' 下标处的括号子串长度，肯定是已经计算好的
                    // 此时，需要减去前面括号自创的长度，判断减去后，是否有多余的 '(' 与当前右括号匹配
                    if(dp[i - 1] == 0) {
                        continue; // 前面的左括号都匹配不到它对应的右括号，更别提当前的右括号了
                    }
                    int left = i - dp[i - 1] - 1;
                    if(left >= 0 && s.charAt(left) == '(') {
                        dp[i] += dp[i - 1] + 2;
                        // 还需要判断 left 左边是否也有完整的括号子串
                        if(left > 0) {
                            dp[i] += dp[left - 1];
                        }
                        res = Math.max(res, dp[i]);
                    }
                }
            }
        }
        return res;
    }
}

---

输出 2