leetcode-最长有效括号

这是我参与8月更文挑战的第21天，活动详情查看：8月更文挑战

可能自己也没想到，可以连续更文21天。
21应该是个有点特别意义的数字，之前可能普遍会认为21天可以养成1个新的习惯。一个比较直接的证据是，前几年有段时间，很多技术类的书籍会取1个名字叫做“21天从入门到精通XXX”，当然后来这也被玩成一个梗了，现在应该出现的是“21天从入门到放弃XXX”。
不过在我看来，养成一个好习惯，不在于多少天，而在于决心和恒心：开始时需要一往无前的决心，想放弃时需要坚持的恒心，说起来简单，没多少人可以真正做到。
不管怎么样，21天应该还是1个小小的里程碑，不过跨过今天，应该还会是一个全新的开始，所需要的，还是决心和恒心。

回到正题，今天继续做leetcode的第32题。

题目

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

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

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

示例 3：
输入：s = ""
输出：0

思路

虽然一开始知道是动态规划的题目，不过自己想了很久没想出来。后来看了其他人的题解，其实就是一个小点没想明白，不过明白了之后，豁然开朗的感觉特别好。
s的长度为len，定义一个长度为len的数组longest[]，代表以当前下标为结束的子串，最长有效括号的长度。一个显而易见的情况是，如果下标i的字符为'('，那不可能是任何1个合法括号字符串的结束，所以此时longest[i] = 0。
接下来讨论下标i的字符为')'的情况，这时考虑倒数第2个字符，如果倒数第2个字符为'('，那么刚好跟最后1个字符组成了有效括号，此时至少longest[i] = 2，如果前面还存在字符，就要再加上以倒数第3个字符为结束的最长有效括号，longest[i] += longest[i-2]。
那如果倒数第2个字符是')'呢？这种情况其实是本题的难点，我们可以这样想，先找到以i-1结束的最长有效括号，然后再看前面1个字符是否是'('来跟i的')'配对，如果存在的话，还需要再往前加上i-1-longest[i-1]为结束的最长有效括号，longest[i-1-longest[i-1]]。
这种情况的示意图，为方便画图，用f[]代表longest[]：

Java版本代码

class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        // 以i下标为结束的字符串的最长有效括号长度
        int[] longest = new int[len];
        longest[0] = 0;
        for (int i = 1; i < len; i++) {
            if ('(' == s.charAt(i)) {
                longest[i] = 0;
            } else {
                if ('(' == s.charAt(i-1)) {
                    // 仅这2位就至少存在合法的括号
                    longest[i] = 2;
                    // 如果前面还有合法的括号，就拼接在前面
                    if (i >= 2) {
                        longest[i] += longest[i - 2];
                    }
                } else {
                    // 连续2个右括号
                    if (i == 1) {
                        // 只有2个右括号
                        longest[i] = 0;
                    } else {
                        int pre = i - 1 - longest[i - 1];
                        if (pre >= 0) {
                            if ('(' == s.charAt(pre)) {
                                longest[i] = longest[i - 1] + 2;
                                // 如果存在前序，需要把前面的子串也拼接上
                                if (pre - 1 >= 0) {
                                    longest[i] += longest[pre - 1];
                                }
                            } else {
                                longest[i] = 0;
                            }
                        } else {
                            // 找不到最左边可以匹配的(
                            longest[i] = 0;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if (longest[i] > ans) {
                ans = longest[i];
            }
        }
        return ans;
    }
}
复制代码