「力扣」第 32 题：最长有效括号

• 题目链接：32. 最长有效括号 (opens new window)

方法一：动态规划

• 理解题意：强调必须连续

• 提示：多写几遍可以搞定的，看自己画的 PPT。

• 讲解的时候，先说清楚动态规划的状态定义（子问题定义），不同子问题之间的联系；

• 细节部分，其实很多时候都是在「空数组」「数组下标越界」。

• 只有「右括号」，才能形成结论

• 情况 1：前面是左括号，看再前面

• 情况 2：前面是右括号，减去右括号的长度，再往前看一个（这里必须要举出具体的例子）

1. 如果是左括号，不能形成「有效」；
2. 如果是有右括号：
3. 右括号前是左括号，一定和最近的匹配：dp[i] = dp[i - 2] + 2
4. 右括号前是右括号，可能形成更长的有效括号：dp[i] = dp[i - 1] + 2 + dp[i - dp[i-1] -1 - 1]

数组下标越界需要单独讨论。

class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        if (len < 2) {
            return 0;
        }

        int res = 0;
        int[] dp = new int[len];
        dp[0] = 0;
        for (int i = 1; i < len; i++){
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = 2 + (i - 2 >= 0 ? dp[i - 2] : 0);
                } else {
                    // s.charAt(i - 1) == ')'
                    int index = i - dp[i - 1] - 1;
                    if (index >= 0 && s.charAt(index) == '(') {
                        dp[i] = 2 + dp[i - 1] + (index - 1 >= 0 ? dp[index - 1] : 0);
                    }
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

方法二：栈

讲清楚 Java 中推荐用 Deque：Stack (Java Platform SE 8 ) (opens new window)

栈是什么原因：

• 栈里存的是下标；

• 如何连起来，栈顶元素的下标。

注意：

• stack.pop() 表示遇到右括号，都要弹出栈：
  • 情况 1：右括号找到了与之匹配的左括号，这个时候我们计算 最长有效括号 的长度；
  • 情况 2：当前右括号没有左括号与之匹配（栈为空），记录一下新的 最长有效括号 可能从这里开始。

所以是先弹出，后加入。表示：如果又遇到没有匹配的右括号，「先弹出，后加入」是更新。

如何记录有效括号的长度：

• （这里很难讲清楚）不是记录弹出的左括号的位置，应该记录弹出了左括号以后，它前面的这个位置，因为有一种情况，连续的情况：(())()

如果栈为空，表示当前「右括号」的前面找不到能构成更长有效括号的「左括号」，所以新的最长有效括号从这里的后面开始。

(8,10]

彩排代码：

心得：看图就能把代码写对。

class Solution {

    public int longestValidParentheses(String s) {
        int len = s.length();

        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                // s.charAt(i) == ')'
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                }
                res = Math.max(res, i - stack.peek());
            }
        }
        return res;
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/stack/solutions-1/0032-longest-valid-parentheses 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。