拼多多二面笔试原题，15分钟没做出来，直接挂了。。。

将 脚本之家 设为“星标⭐”第一时间收到文章更新本文经数据结构和算法（id:sjjghsf）授权转载

这道题是LeetCode的第32题，难度为困难。一网友在拼多多的二面笔试中遇到这道题，不过很遗憾的是没做出来，结果直接挂了。拼多多现在也越来越像字节看齐了，面试专考难的。

一般来说一面能过说明技术都不算太差，结果一面过了挂在了二面的算法中，真的是不应该，我们来看下这题除了在拼多多的面试中出现，还有哪些大厂考过。

我们看到拼多多，华为，字节，腾讯，网易都考过这题，所以如果想要进大厂，最好把这题完全掌握。

问题描述

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

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

示例 1：

输入：s = "(()"

输出：2

解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"

输出：4

解释：最长有效括号子串是 "()()"

使用栈解决

这题让求的是最长有效括号长度，一个有效的括号一定是满足下面两个条件：

• 左括号和右括号的数量一定是相等的。
  
• 在有效括号的任何位置左括号的数量一定是大于等于右括号的数量。

根据这两个特性我们可以使用栈来解决，栈中存放的是字符的下标，解决思路就是：

• 如果遇到左括号我们就把他的下标压栈。
• 如果遇到右括号，栈顶元素出栈，如果栈不为空说明出栈的元素和这个右括号匹配，我们需要计算他们的长度，保留最大值即可。如果栈为空，直接把这个右括号所在的下标压栈。

这里要注意如果给定的字符串从一开始就是有效的括号，比如"()())"前4个符号是有效的括号，我们是没法计算他的长度的，因为第一个字符前面是没有字符的，所以我们默认第一个字符前面的下标是-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]就会有下面几种情况：

• 第i个字符是左括号"("，那么以他结尾的是构不成有效括号的，所以dp[i]=0;

• 第i个字符是右括号")"，那么以他结尾的是有可能构成有效括号的，所以还需要继续判断：

1. 这里我们需要判断他前面的也就是第i-1个字符，如果第i-1个字符是左括号"("，类似于……()，那么最长有效括号就是第i-2个字符之前构成的最长有效括号+2，也就是dp[i]=dp[i-2]+2。

2. 如果第i-1个字符也是右括号")"，类似于……((……))，如下图所示，我们还需要判断第i -1- dp[i - 1]个字符是否是左括号"(",如果是"("，那么递推公式是dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]，这里dp[i - dp[i - 1] - 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;
}

  推荐阅读：