其他
拼多多二面笔试原题，15分钟没做出来，直接挂了。。。
The following article is from 数据结构和算法 Author 博哥
这道题是LeetCode的第32题，难度为困难。一网友在拼多多的二面笔试中遇到这道题，不过很遗憾的是没做出来，结果直接挂了。拼多多现在也越来越像字节看齐了，面试专考难的。
一般来说一面能过说明技术都不算太差，结果一面过了挂在了二面的算法中，真的是不应该，我们来看下这题除了在拼多多的面试中出现，还有哪些大厂考过。
我们看到拼多多，华为，字节，腾讯，网易都考过这题，所以如果想要进大厂，最好把这题完全掌握。
问题描述
难度：困难
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
使用栈解决
左括号和右括号的数量一定是相等的。 在有效括号的任何位置左括号的数量一定是大于等于右括号的数量。
如果遇到左括号我们就把他的下标压栈。 如果遇到右括号，栈顶元素出栈，如果栈不为空说明出栈的元素和这个右括号匹配，我们需要计算他们的长度，保留最大值即可。如果栈为空，直接把这个右括号所在的下标压栈。
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;
}
动态规划
第i个字符是左括号"("，那么以他结尾的是构不成有效括号的，所以dp[i]=0;
第i个字符是右括号")"，那么以他结尾的是有可能构成有效括号的，所以还需要继续判断：
这里我们需要判断他前面的也就是第i-1个字符，如果第i-1个字符是左括号"("，类似于……()，那么最长有效括号就是第i-2个字符之前构成的最长有效括号+2，也就是dp[i]=dp[i-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]是第一个省略号构成的有效括号长度，这个不要忘了。
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;
}