第六章 - 高频考题(困难)
0032. 最长有效括号

题目地址(32. 最长有效括号)

题目描述

1
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
2
3
示例 1:
4
5
输入: "(()"
6
输出: 2
7
解释: 最长有效括号子串为 "()"
8
示例 2:
9
10
输入: ")()())"
11
输出: 4
12
解释: 最长有效括号子串为 "()()"
Copied!

前置知识

  • 动态规划

暴力(超时)

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

符合直觉的做法是:分别计算以 i 开头的 最长有效括号(i 从 0 到 n - 1·),从中取出最大的即可。

代码

代码支持: Python
1
class Solution:
2
def longestValidParentheses(self, s: str) -> int:
3
n = len(s)
4
ans = 0
5
6
def validCnt(start):
7
# cnt 为 ) 的数量减去 ( 的数量
8
cnt = 0
9
ans = 0
10
for i in range(start, n):
11
if s[i] == '(':
12
cnt += 1
13
if s[i] == ')':
14
cnt -= 1
15
if cnt < 0:
16
return i - start
17
if cnt == 0:
18
ans = max(ans, i - start + 1)
19
return ans
20
for i in range(n):
21
ans = max(ans, validCnt(i))
22
23
return ans
Copied!
复杂度分析
  • 时间复杂度:$O(N^2)$
  • 空间复杂度:$O(1)$

思路

主要思路和常规的括号解法一样,遇到'('入栈,遇到')'出栈,并计算两个括号之间的长度。 因为这个题存在非法括号对的情况且求是合法括号对的最大长度 所以有两个注意点是:
  1. 1.
    栈中存的是符号的下标
  2. 2.
    当栈为空时且当前扫描到的符号是')'时,需要将这个符号入栈作为分割符
  3. 3.
    栈中初始化一个 -1,作为分割符

代码

  • 语言支持: Python, javascript, CPP
javascript code:
1
// 用栈来解
2
var longestValidParentheses = function (s) {
3
let stack = new Array();
4
let longest = 0;
5
stack.push(-1);
6
for (let i = 0; i < s.length; i++) {
7
if (s[i] === "(") {
8
stack.push(i);
9
} else {
10
stack.pop();
11
if (stack.length === 0) {
12
stack.push(i);
13
} else {
14
longest = Math.max(longest, i - stack[stack.length - 1]);
15
}
16
}
17
}
18
return longest;
19
};
Copied!
Python Code:
1
class Solution:
2
def longestValidParentheses(self, s: str) -> int:
3
if not s:
4
return 0
5
res = 0
6
stack = [-1]
7
for i in range(len(s)):
8
if s[i] == "(":
9
stack.append(i)
10
else:
11
stack.pop()
12
if not stack:
13
stack.append(i)
14
else:
15
res = max(res, i - stack[-1])
16
return res
Copied!
CPP Code:
1
class Solution {
2
public:
3
int longestValidParentheses(string s) {
4
stack<int> st;
5
st.push(-1);
6
int ans = 0;
7
for (int i = 0; i < s.size(); ++i) {
8
if (s[i] == ')' && st.top() != -1 && s[st.top()] == '(') {
9
st.pop();
10
ans = max(ans, i - st.top());
11
} else st.push(i);
12
}
13
return ans;
14
}
15
};
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

O(1) 空间

思路

我们可以采用解法一中的计数方法。
  • 从左到右遍历一次,并分别记录左右括号的数量 left 和 right。
  • 如果 right > left ,说明截止上次可以匹配的点到当前点这一段无法匹配,重置 left 和 right 为 0
  • 如果 right == left, 此时可以匹配,此时有效括号长度为 left + right,我们获得一个局部最优解。如果其比全局最优解大,我们更新全局最优解
值得注意的是,对形如 (((() 这样的,更新全局最优解的逻辑永远无法执行。一种方式是再从右往左遍历一次即可,具体看代码。
类似的思想有哨兵元素,虚拟节点。只不过本题无法采用这种方法。

代码

代码支持:Java,Python3, CPP
Java Code:
1
public class Solution {
2
public int longestValidParentheses(String s) {
3
int left = 0, right = 0, maxlength = 0;
4
for (int i = 0; i < s.length(); i++) {
5
if (s.charAt(i) == '(') {
6
left++;
7
} else {
8
right++;
9
}
10
if (left == right) {
11
maxlength = Math.max(maxlength, left + right);
12
}
13
if (right > left) {
14
left = right = 0;
15
}
16
}
17
left = right = 0;
18
for (int i = s.length() - 1; i >= 0; i--) {
19
if (s.charAt(i) == '(') {
20
left++;
21
} else {
22
right++;
23
}
24
if (left == right) {
25
maxlength = Math.max(maxlength, left + right);
26
}
27
if (left > right) {
28
left = right = 0;
29
}
30
}
31
return maxlength;
32
}
33
}
Copied!
Python3 Code:
1
class Solution:
2
def longestValidParentheses(self, s: str) -> int:
3
ans = l = r = 0
4
for c in s:
5
if c == '(':
6
l += 1
7
else:
8
r += 1
9
if l == r:
10
ans = max(ans, l + r)
11
if r > l:
12
l = r = 0
13
l = r = 0
14
for c in s[::-1]:
15
if c == '(':
16
l += 1
17
else:
18
r += 1
19
if l == r:
20
ans = max(ans, l + r)
21
if r < l:
22
l = r = 0
23
24
return ans
Copied!
CPP Code:
1
class Solution {
2
public:
3
int longestValidParentheses(string s) {
4
int left = 0, right = 0, ans = 0, N = s.size();
5
for (int i = 0; i < N; ++i) {
6
left += s[i] == '(';
7
right += s[i] == ')';
8
if (left == right) ans = max(ans, left + right);
9
else if (right > left) left = right = 0;
10
}
11
left = 0, right = 0;
12
for (int i = N - 1; i >= 0; --i) {
13
left += s[i] == '(';
14
right += s[i] == ')';
15
if (left == right) ans = max(ans, left + right);
16
else if (left > right) left = right = 0;
17
}
18
return ans;
19
}
20
};
Copied!

动态规划

思路

所有的动态规划问题, 首先需要解决的就是如何寻找合适的子问题. 该题需要我们找到最长的有效括号对, 我们首先想到的就是定义dp[i]为前 i 个字符串的最长有效括号对长度, 但是随后我们会发现, 这样的定义, 我们无法找到 dp[i]和 dp[i-1]的任何关系. 所以, 我们需要重新找一个新的定义: 定义dp[i]为以第 i 个字符结尾的最长有效括号对长度. 然后, 我们通过下面这个例子找一下 dp[i]和 dp[i-1]之间的关系.
1
s = '(())())'
Copied!
从上面的例子我们可以观察出一下几点结论(描述中 i 为图中的 dp 数组的下标, 对应 s 的下标应为 i-1, 第 i 个字符的 i 从 1 开始).
  1. 1.
    base case: 空字符串的最长有效括号对长度肯定为 0, 即: dp[0] = 0;
  2. 2.
    s 的第1个字符结尾的最长有效括号对长度为 0, s 的第2个字符结尾的最长有效括号对长度也为 0, 这个时候我们可以得出结论: 最长有效括号对不可能以'('结尾, 即: dp[1] = d[2] = 0;
  3. 3.
    当 i 等于 3 时, 我们可以看出 dp[2]=0, dp[3]=2, 因为第 2 个字符(s[1])和第 3 个字符(s[2])是配对的;
    当 i 等于 4 时, 我们可以看出 dp[3]=2, dp[4]=4, 因为我们配对的是第 1 个字符(s[0])和第 4 个字符(s[3]);
    因此, 我们可以得出结论: 如果第i个字符和第i-1-dp[i-1]个字符是配对的, 则 dp[i] = dp[i-1] + 2, 其中: i-1-dp[i-1] >= 1, 因为第 0 个字符没有任何意义;
  4. 4.
    根据第 3 条规则来计算的话, 我们发现 dp[5]=0, dp[6]=2, 但是显然, dp[6]应该为 6 才对, 但是我们发现可以将"(())"和"()"进行拼接, 即: dp[i] += dp[i-dp[i]], 即: dp[6] = 2 + dp[6-2] = 2 + dp[4] = 6
根据以上规则, 我们求解 dp 数组的结果为: [0, 0, 0, 2, 4, 0, 6, 0], 其中最长有效括号对的长度为 6. 以下为图解:

代码

代码支持:Python3, CPP
Python3 Code:
1
class Solution:
2
def longestValidParentheses(self, s: str) -> int:
3
mlen = 0
4
slen = len(s)
5
dp = [0] * (slen + 1)
6
for i in range(1, len(s) + 1):
7
# 有效的括号对不可能会以'('结尾的
8
if s[i - 1] == '(':
9
continue
10
11
left_paren = i - 2 - dp[i - 1]
12
if left_paren >= 0 and s[left_paren] == '(':
13
dp[i] = dp[i - 1] + 2
14
15
# 拼接有效括号对
16
if dp[i - dp[i]]:
17
dp[i] += dp[i - dp[i]]
18
19
# 更新最大有效扩对长度
20
if dp[i] > mlen:
21
mlen = dp[i]
22
23
return mlen
Copied!
CPP Code:
1
class Solution {
2
public:
3
int longestValidParentheses(string s) {
4
vector<int> dp(s.size() + 1, 0);
5
int ans = 0;
6
for (int i = 0; i < s.size(); ++i) {
7
if (s[i] == '(') continue;
8
int start = i - dp[i] - 1;
9
if (start >= 0 && s[start] == '(')
10
dp[i + 1] = dp[i] + 2 + dp[start];
11
ans = max(ans, dp[i + 1]);
12
}
13
return ans;
14
}
15
};
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

关键点解析

  1. 1.
    第 3 点特征, 需要检查的字符是 s[i-1]和 s[i-2-dp[i-1]], 根据定义可知: i-1 >= dp[i-1], 但是 i-2 不一定大于 dp[i-1], 因此, 需要检查越界;
  2. 2.
    第 4 点特征最容易遗漏, 还有就是不需要检查越界, 因为根据定义可知: i >= dp[i], 所以 dp[i-dp[i]]的边界情况是 dp[0];

相关题目

扩展

  1. 1.
    如果判断的不仅仅只有'('和')', 还有'[', ']', '{'和'}', 该怎么办?
  2. 2.
    如果输出的不是长度, 而是任意一个最长有效括号对的字符串, 该怎么办?
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。