LeetCode 32. 最长有效括号：栈与动态规划详解，拼多多等大厂高频面试题

这道题是 LeetCode 的第 32 题，难度为困难。最近有网友在拼多多的二面笔试中遇到了这道题，遗憾的是在限定时间内没能做出来，结果面试直接挂了。如今不少大厂的面试，尤其是像拼多多、字节这样的公司，对算法题的考察越来越有挑战性。

通常来说，能通过技术一面说明基础能力并不差，结果却挂在二面的算法题上，确实有些可惜。这道题不仅在拼多多的面试中出现过，我们来看看还有哪些大厂曾考过它。

从网友们的讨论来看，拼多多、华为、字节、腾讯、网易等公司的面试中都出现过这道题。因此，如果你的目标是进入这些大厂，彻底掌握这道题是很有必要的。

问题描述

来源：LeetCode 第32题
难度：困难

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

示例 1：

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

示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

使用栈解决

这道题要求的是最长有效括号的长度。一个有效的括号子串必须满足两个核心条件：

1. 左括号和右括号的数量相等。
2. 在子串的任何位置，左括号的数量都大于或等于右括号的数量。

基于这两个特性，我们可以利用栈来解决。栈中存放的是字符的下标，具体的解决思路如下：

• 遇到左括号 '('，将其下标压入栈中。
• 遇到右括号 ')'，将栈顶元素出栈。
  • 如果出栈后栈不为空，说明出栈的左括号下标与当前右括号匹配成功。此时计算当前有效长度（当前下标 - 栈顶下标），并更新最大值。
  • 如果出栈后栈为空，说明当前右括号没有与之匹配的左括号，它是一个无效的分隔点。此时将当前右括号的下标压入栈中，作为新的“基准点”。

这里有一个关键点：如果字符串从一开始就是有效的括号，例如”()())”的前四个字符，我们无法直接计算长度，因为第一个有效括号对前面没有参照下标。为了解决这个问题，我们可以在开始时先将 -1 压入栈中，作为一个虚拟的“基准点”。

以示例 2 ”)()())” 为例，我们通过图示来理解栈的变化过程：

以下是具体的代码实现：

public int longestValidParentheses(String s) {
    int max = 0; // 记录最大长度
    Stack<Integer> stack = new Stack<>(); // 栈
    stack.push(-1); // 先把-1压栈
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i); // 遇到左括号，下标压栈
        } else {
            stack.pop(); // 遇到右括号，栈顶元素先出栈。
            if (stack.empty()) {
                // 如果栈为空，把这个右括号的下标压栈。
                stack.push(i);
            } else {// 计算长度，保存最大值。
                max = Math.max(max, i - stack.peek());
            }
        }
    }
    return max;
}

动态规划

除了栈，我们也可以用动态规划的思路来解决。定义 dp[i] 表示以字符 s[i] 为结尾的最长有效括号子串的长度。计算 dp[i] 时，我们需要根据 s[i] 的值进行分情况讨论：

• 情况一：如果 s[i] 是左括号 '('，那么以它结尾不可能构成有效括号，因此 dp[i] = 0。
• 情况二：如果 s[i] 是右括号 ')'，那么它有可能构成有效括号，需要进一步判断前一个字符 s[i-1]。
  1. 如果 s[i-1] 是左括号 '('，形如 ……()，那么状态转移方程为：dp[i] = dp[i-2] + 2。
  2. 如果 s[i-1] 是右括号 ')'，形如 ……((……))，如下图所示。我们需要检查 s[i - 1 - dp[i-1]] 这个字符（即与当前 ')' 可能匹配的左括号位置）是否是 '('。如果是，则状态转移方程为：dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]。这里的 dp[i - dp[i-1] - 2] 表示更早之前形成的有效括号子串长度，不能遗漏。

为了使下标计算更方便，我们可以在字符串前添加一个虚拟字符（如 ')'），让有效计算从 i=2 开始。代码如下：

public int longestValidParentheses(String s) {
    int max = 0;
    s = ")" + s; // 这里为了方便计算前面加个右括号
    int dp[] = new int[s.length()];
    for (int i = 2; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            // 递推公式
            if (s.charAt(i - 1) == '(') {
                dp[i] = dp[i - 2] + 2;
            } else if (s.charAt(i - dp[i - 1] - 1) == '(') {
                dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
            }
            max = Math.max(max, dp[i]); // 保存最大值
        }
    }
    return max;
}

总结

“最长有效括号”是一道经典的动态规划与栈应用题目，也是大厂面试中的高频考点。栈的解法思路清晰，通过维护下标来定位有效区间；动态规划的解法则体现了对问题状态的精细划分和递推关系。掌握这两种解法，不仅能帮助你应对类似面试题，更能加深对栈和动态规划这两种重要算法思想的理解。

如果你在准备技术面试的过程中遇到了其他难题，或者想系统性地提升自己的算法能力，欢迎到 云栈社区 的算法与数据结构板块，和更多开发者一起交流讨论。