在本讲，我将带你继续探究“一题多解”，结合前面学习过且面试常考的知识点，比如区间问题、双指针、动态规划、栈、贪心，从多个角度去求解一个题目，通过逐步分析已知条件、提取题目特点，进而将不熟悉的题目变成我们擅长求解的题目，最终攻克“最长有效括号长度”的难题。
在正式介绍前，我有两点说明。
这类题目的解法非常多，但本讲仅重点介绍其中 5 种具有代表性的解法。目的是让你在算法面试时，能够展开更多的解题思路。
并不是每种解法都能够利用常量空间，如果用到，我会特别注明。
题目
给你一个只包含
('
和
‘)’
的字符串，找出最长有效（格式正确且连续）括号子串的长度。
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
注意，“有效”需要满足两个条件：
连续子串；
子串有效指的是每个左括号 ‘(’ 都可以找到相应的右括号 ‘)’ 完成一一配对。
在“01 | 栈：从简单栈到单调栈，解决经典栈问题”的“例 1”中，我们介绍过如何判断一个字符串是否合法（即有效）。只不过，在这个题中，我们要从一个字符串中找到一个子串，需要满足“最长且合法”。
当我们拿到题目，最容易想到的思路是：
一共有 O(N2) 个连续子串
判断每个连续子串是否合法
如果直接按上述思路开始进行暴力求解，那么时间复杂度就会上升到 O(N3)。因此，在求解前，我们应该根据已知条件，认真分析题目的特点，然后和暴力破解法 Say GoodBye。
合法字符串的特性
首先我们看一下合法字符串长什么样？有什么样的特点？一般而言，括号对匹配成功的合法字符串，有三种情况。
相连：指很多个配对成功的括号连在一起，比如 ["()", “()()”, “()()()”]。
嵌套：指内外层层相套，但是它们能够合法配对成功，比如 ["()", “(())”, “((()))”]。
相连 + 嵌套：指相连和嵌套混合的情况，但是它们是合法的字符串，比如 ["()(())", “(())()”]。
注意，在后文中，我们将用“相连”“嵌套”“相连+嵌套”特指这三种情况。
特点 1： 区间
我们发现，括号能够配对的时候，总是有一个左括号 + 一个右括号，如果我们将左括号的下标当成一个区间的左端点，右括号的下标当成一个区间的右端点。
那么用区间来表示一个合法字符串，会得到什么有趣的特点呢？下面我们仍然从合法字符串的 3 种情况展开。
相连：比如"()()()"，就可以得到区间 [[0,1], [2,3], [4,5]]。
嵌套：比如"(())"，就可以得到区间 [[0,3], [1,2]]。
相连+嵌套：比如"()(())"，就可以得到区间 [[0,1], [2,5], [3,4]]。
我们尝试定义一下区间的连接性。
如果两个区间 <a, b>, <c, d> 满足下面 2 个条件之一：
有公共点，即 not ( (b < c) || d < a) )；
b < c && b + 1 == c 或者 d < a && d + 1 == a。
我们就称这两个区间具有连接性。
我这里给出三个例子，帮你理清区间的连接性。
例 1：区间 [1,2], [3,4] 是否具有连接性？答案是！因为区间 [1,2] 的右端点 2 加上 1 就是区间 [3,4] 的左端点（满足条件 2）。
例 2：区间 [0,5] 和区间 [2,5] 是否具有连接性？答案是！因为它们是有公共点的，因此我们认为它们具有连接性。
例 3：区间 [0, 1] 和区间 [3,4] 则不具有连接性。因为这两个区间不满足条件 1，也不满足条件 2。
那么定义好区间的连接性之后，有什么用途呢？这样操作后，我们就可以把原始的题目分为两步：
得到所有配对的左括号与右括号的下标；
给定一系列区间，找到最长的区域，这个区域被具有相连性的区间覆盖。
针对第 2 步，我们进一步举例说明。
例 1：当给定的区间为 [1, 2], [3,4] 的时候，我们可以找到一个最长的区域 [1, 4]，这个区域是由具有相连性的两个区间覆盖的。
例 2：当给定的区间集合为 [0, 1], [3,4], [5,6], [6,9] 的时候，最长的区域为 [3, 9]。由 [3,4], [5,6], [6,9] 这三个具有相连性的区间覆盖。
注意，我们不要求区域内的区间两两满足相连性。
比如 [3,4] 和 [5,6] 具有连接性，但是 [3,4] 和 [6,9] 不具有连接性。在操作时，我们可以这样操作：
Step 1. [3,4] 和 [5,6] 具有连接性，合并成一个大区间 [3,6]；
Step 2. [3,6] 与 [6,9] 具有连接性，合并成一个大区间 [3,9]。
例 3：给定一个区间 [0, 1]，那么最长区域就是 [0, 1]。
注意：一个合法的括号配对字符串不会生成一个单独的很长的区间，比如 [0, 10]。如果 s[0]= ‘(’ 与 s[10]=’)’ 配对成功，那么必然是一种嵌套的合法字符串，内部还会有很多区间必须要给出来。
第一步的处理，可以直接使用栈（参考“01 | 栈：从简单栈到单调栈，解决经典栈问题”的“例 1”）。而第二步的处理需要用到贪心算法（参考“11 | 贪心：这种思想，没有模板，如何才能掌握它？”的“例 2”）。
基于这样的思路，我们就可以写出代码如下（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
class Solution {
public int longestValidParentheses(String s) {
// 采用重叠的最长的区间的做法
final int N = s == null ? 0 : s.length();
// 两两配对的时候，我们将它们看成一个区间
// 配对的时候，需要用到栈
Stack<Integer> st = new Stack<>();
// 用来存放区间
List<int[]> ranges = new ArrayList<>();
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
// 是否配对成功？
if (c == ')') {
if (!st.isEmpty()) {
final int topIdx = st.pop();
ranges.add(new int[]{topIdx, i});
}
} else {
st.push(i);
}
}
// 将区间两端点进行排序
Collections.sort(ranges, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
// 由于得到了很多区间，我们需要取相互覆盖的区间的最长值
// 比如，我们认为[3,4], [5,6]是相互连续且覆盖的区间
int start = 0;
int end = -1;
int ans = 0;
for (int i = 0; i < ranges.size(); i++) {
final int from = ranges.get(i)[0], to = ranges.get(i)[1];
// 如果和[start, end]这个区间相连
if (from <= end + 1) {
end = Math.max(end, to);
} else {
// 如果不相连!
start = from;
end = to;
}
ans = Math.max(ans, end - start + 1);
}
return ans;
}
}
|
代码：Java/C++/Python
复杂度分析：从字符串中提取区间，只需要 O(N) 的时间复杂度。然后我们需要对区间进行排序，最差情况下有 O(N/2) 个区间，那么排序的时间复杂度会上升到 O(NlgN)。最后的贪心算法时间复杂度为 O(N)。因此，整个问题的时间复杂度为 O(NlgN)，空间复杂度为 O(N)。
关于求解最长相连通的区间问题，这里我还给你留了一个练习题。你可以做一做。
练习题 1：给定一系列区间，将重合的区间合并在一起。
输入：A = [[1,2], [2,3], [2,6], [7, 8]]
输出：[[1, 6], [7,8]]
代码：Java/C++/Python
我们发现，实际上整个问题的时间复杂度是由排序带来的，那么，有没有可能优化掉排序呢？我们先来看一下题目中生成区间的代码：
1
2
3
4
5
6
|
if (c == ')') {
if (!st.isEmpty()) {
final int topIdx = st.pop();
ranges.add(new int[]{topIdx, i});
}
}
|
不难发现，在右括号找到左括号匹配成功的时候，总是记录下左括号下标<，右括号下标 >。
题目中，左括号的下标本来就是有序的，那么我们可以使用一个数组 pairPos[] 来记录这个匹配成功的区间信息。采用的原则如下：
pairPos[左括号的下标] = 右括号的下标pairPos[右括号的下标] = -1
就是下图所示的样子：
也就意味着，我们将区间信息成对放在了 <i, pairPos[i]>，其中 i 是一个字符串中配对成功的左括号的下标。
那么，基于这个思想，我们可以优化代码如下（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
class Solution {
public int longestValidParentheses(String s) {
// 采用重叠的最长的区间的做法
final int N = s == null ? 0 : s.length();
// 两两配对的时候，我们将它们看成一个区间
// 配对的时候，需要用到栈
Stack<Integer> st = new Stack<>();
// 记录每个点对应的位置
int[] pairPos = new int[N];
Arrays.fill(pairPos, -1);
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
if (!st.isEmpty()) {
final int topIdx = st.pop();
pairPos[topIdx] = i;
}
} else {
st.push(i);
}
}
// 由于得到了很多区间，我们需要取相互覆盖的区间的最长值
// 比如，我们认为[3,4], [5,6]是相互连续且覆盖的区间
int start = 0;
int end = -1;
int ans = 0;
for (int i = 0; i < N; i++) {
if (pairPos[i] == -1) {
continue;
}
final int from = i, to = pairPos[i];
// 如果和[start, end]这个区间相交
if (from <= end + 1) {
end = Math.max(end, to);
} else {
// 如果不相交!
start = from;
end = to;
}
ans = Math.max(ans, end - start + 1);
}
return ans;
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(N)。
接下来我们再看题目的另外一个特点，连续性。
特点 2：连续性
通过“特点 1”的分析，我们将问题处理成区间的连接性问题。不难发现，所谓相连性，就是要求：
求解出来的最长区间，里面的每个字符都可以配对成功。
那么，这个条件必然等价于，这个区间里面的下标，一旦排序之后，必然由相邻的整数构成。下面我们分别举例进行说明。
相连：比如 “()()()"，就可以得到区间 [[0,1], [2,3], [4,5]]。排序后，得到整数列表 [0,1,2,3,4,5]。
嵌套：比如 “(())"，就可以得到区间 [[0,3], [1,2]]。排序后，得到整数列表 [0,1,2,3]
相连+嵌套：比如 “()(())"，就可以得到区间 [[0,1], [2,5], [3,4]]。排序后，得到整数列表 [0,1,2,3,4,5]。
当找到一个不能匹配的位置 NOT 的时候，我们不可能在 NOT 的左边找一个位置 left_pos，在 NOT 的右边找一个位置 right_pos，并且使得 [left_pos, right_pos] 是一个合法的字符串。
上面描述的情况如下图所示：
我们可以使用反证法进行证明。
证明：假设存在一个位置 NOT，不能找到一个左括号与之匹配。但是我们可以找到 left_pos < NOT 和 right_pos > NOT，并且使得 [left_pos, right_pos] 是一个合法括号的字符串。
首先，由于 [left_pos, right_pos] 是一个合法的括号配对的子串，那么可以肯定，这个区间里面的每一个字符应该都有左括号与之匹配。但是这一结论与“NOT 找不到左括号匹配”相矛盾。因此，我们就证明了合法字符串的连续性。
那么，我们是不是可以进行如下操作呢？
Step 1. 把所有配对成功的下标，都放到一个数组中，然后再把这个数组排序。
Step 2. 找到最长的相邻整数构成的列表，输出其长度。
为了方便你理解 Step 2 中“最长的相邻整数构成的列表”，这里我给你举个例子：
当给定的数组为 A[] = {0,1,3,4,5,6,8,9} 时，最长的相邻整数列表为 [3,4,5,6]，输出长度 4。
那么，基于这样的思路，我们可以写出代码如下（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
}
// 拿到所有的区间
List<Integer> pairs = new ArrayList<>();
// 栈
Stack<Integer> st = new Stack<>();
for (int i = 0; i < N; i++) {
// 我们想找到每个位置匹配的地方
final char c = s.charAt(i);
if (c == ')') {
if (!st.empty()) {
// 我们可以找到i匹配的位置中st.top();
final int idx = st.pop();
pairs.add(idx);
pairs.add(i);
}
} else {
st.push(i);
}
}
// 我们将pairs放在一起，然后排个序
Collections.sort(pairs);
// 记录最长的匹配连续区域
int ans = 0;
// 所有的匹配成功的区域，都是连在一起的
// 那么把序之后，这些数字应该是连续的，中间没有中断过
int preValue = -1;
int rangeStart = 0;
for (int i = 0; i < pairs.size(); i++) {
// 拿到当前值
final int cur = pairs.get(i);
// 如果之前有值
if (i > 0) {
// 如果值不再连续
if (cur != preValue + 1) {
// 那么从[rangeStart, i)就是一个合法区间
ans = Math.max(ans, i - rangeStart);
rangeStart = i;
}
}
preValue = cur;
}
ans = Math.max(ans, pairs.size() - rangeStart);
return ans;
}
}
|
代码：Java/C++/Python
复杂度分析：最差情况下，会有 N 个整数放到数组中排序，所以时间复杂度为 O(NlgN)，空间复杂度为 O(N)。
我们继续从相连性出发，请你思考，这里是否必须要做排序？既然都相连了，我们就把所有配对成功的字符标记为 1，没有配对成功的字符标记为 -INF，如下图所示：
那么，原问题就成功转化为“求一个数组的最大子数组”问题。并且，最大子数组和即是原问题的输出。
基于这个思想，我们可以写出代码如下（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
}
// 我们要找到每个位置对应的pair在什么地方
int[] pairPos = new int[N];
Arrays.fill(pairPos, -1);
Stack<Integer> st = new Stack<>();
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
// 如果遇到右括号，我们看看能不能找到匹配的位置
if (c == ')') {
// 如果可以找到匹配的位置
if (!st.isEmpty()) {
pairPos[i] = st.peek();
pairPos[st.peek()] = i;
st.pop();
}
} else {
st.push(i);
}
}
// 接下来，我们只需要在pairPos数组中找到连续的，中间不带-1的
// 最长的就可以了
int tmp_sum = 0;
int max_sum = 0;
for (int i = 0; i < N; i++) {
// 如果遇到了-1，那么我们就让tmp_sum变得足够小
final int v = (pairPos[i] == -1) ? Integer.MIN_VALUE / 2 : 1;
tmp_sum = Math.max(tmp_sum, 0) + v;
max_sum = Math.max(max_sum, tmp_sum);
}
return max_sum;
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(N)。
然后，我们再看一下这个题目的下一个特点与解法。
特点 3：最长
我们从题目中看到了“最长”二字，这不禁让我想起一个总结：
如果题目中出现“最大”“最小”“最长”等字眼，那么可以尝试往 DP 的方向思考。
因此，这里我们就尝试往 DP 的方向去想一想，首先还是拿出“ DP 分析 6 步法”。
1. 最后一步
DP 问题的关键是最后一步。对于处理一维的字符串而言，最后一步肯定就是处理字符串的最后一个字符。最后一个字符可以分为两种情况：左括号、右括号。
左括号：此时肯定找不到括号与这个字符配对，所以包含最后一个字符的有效子串长长度为 0。
右括号：如果最后一个字符为右括号，那么我们再看它前面的那个字符，这个字符也只有 2 种情况（左括号，右括号）。
1） 左括号
情况如下图所示：
此时，最后一个字符可以和它前面的字符配对成功。但是需要注意：包含最后一个括号的合法子串长度可能是 2，也可能比 2 大。因为可能有如下 2 种情况：
情况 1，前面字符串不是有效的合法子串，此时最后一个括号的合法子串长度是 2。如下图所示：
情况 2，前面的字符串也是有效的合法子串。我们需要加上这部分的合法子串的长度。此时最后一个括号的合法子串长度大于 2。如下图所示：
2）右括号
如果最后一个括号之前的字符是右括号，如下图所示：
那么我们只需要跳过前面那一段有效合法子串，看一下“问号”位置（与最后一个字符可能匹配的位置 pairPos）是否可以与最后一个字符匹配。
如果问号位置（s[pairPos]）是一个右括号，那么最后一个字符肯定匹配失败；
如果问号位置（s[pairPos]）是一个左括号，那么就可以配对成功。
在配对成功的情况下，我们还需要加上之前的合法子串的长度。情况如下：
我们可以将这里分情况的思路用思维导图整理如下：
分情况讨论总是很烦，所以这里我给你总结成两条原则：
配对失败，那么此字符的合法子串长度为 0；
配对成功，还需要加上之前的合法长度。
2. 子问题
我们可以用 f(x) 表示以字符 s[x] 为右端点的，合法子串的长度。
3. 递推关系
有了"f(x)” 的含义，可以写出递推的伪代码如下（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
|
// 我们要求解 f(i)
if s[i-1] == '(':
f(i) = 2 + f(i-2) // 加上前面合法的子串长度
else:
preValidLen = f(i-1)
// 找到问号位置
pairPos = i - preLen - 1
if pairPos >= 0 and s[pairPos] == '(':
f(i) = i + 1 - pairPos
if pairPos - 1 >= 0: // 如果之前还有合法的子串
f(i) += f(pairPos-1)
|
4. f(x) 的表达
我们发现，x 只是字符串 s 的下标，那么只需使用一个一维的数组 dp[] 就可以表示 f(x) 了。
5. 初始条件与边界
在计算的时候，f(i) 会依赖 f(i-1) 以及 f(i-2)，还有 f(pairPos-1)。这里提醒我们：
由 f(i)依赖 f(i-1)、f(i-2)，可知初始计算的时候，至少应该先计算出两项的值，也就是计算出 f(0) 和 f(1)；
由于我们并不清楚f(pairPos-1)具体的值是多少，所以在处理的时候，要注意判断是否越界。
6. 计算顺序
如果我们从左往右遍历字符串，那么计算的时候，需要注意：
处理字符串为空，或者长度为 1 的特殊情况；
优先计算头两个字符的 f() 函数值；
注意 pairPos 的越界的处理。
至此，我们就可以写出动态规划求解的代码了（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
class Solution {
public int longestValidParentheses(String s) {
// 拿到字符串的长度
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
}
int[] dp = new int[N];
int ans = 0;
// 前面两个字符的情况
// 只有当()为字符串的时候，这两个是dp[0] = 0, dp[1] = 2;
// 其他都是dp[0] = dp[1] = 0;
if (s.charAt(0) == '(' && s.charAt(1) == ')') {
dp[1] = 2;
ans = 2;
}
for (int i = 2; i < N; i++) {
final char c = s.charAt(i);
// dp[i] = 0; // java的数组默认会初始化
// 所以dp[i] = 0;可以跳过
if (c == ')') {
// 看一下preChar
final char preChar = s.charAt(i - 1);
if (preChar == '(') {
// 前面是xxx()的结构
dp[i] = 2 + dp[i - 2];
} else {
// 前面是一个 xxx))的结构
// 那么只需要找到更之前的字符就可以了
final int preLen = dp[i - 1];
// [start, i-1] = preLen
// i - start = preLen
final int start = i - preLen;
// 那么找到与 i 配对的位置
final int pairPos = start - 1;
if (pairPos >= 0 && s.charAt(pairPos) == '(') {
// 如果能够与i匹配成功
// 那么形成的结构就是xx((xxxx))
// 我们还需要看一下之前的长度是不是可以加上去
int curLen = i + 1 - pairPos;
// 之前还有长度吗？
if (pairPos - 1 >= 0) {
curLen += dp[pairPos - 1];
}
dp[i] = curLen;
}
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(N)。
在使用 DP 的过程中，我们发现，可以浓缩成一个原则：
配对成功，就加上之前的合法长度。
那么，基于这个原则我们还有没有其他解法呢？
特点 4：栈的性质
在特点 1 和特点 2 中，都用到了栈来找到每一个字符的匹配字符的位置（如果存在）。下面我们再看一下，当一个合法的字符串利用栈来进行匹配处理的时候，有什么样的性质。
1
2
3
4
5
6
7
8
9
10
11
12
|
stack = []
for i in range(len(s)):
if s[i] == ')':
if not stack.empty():
topIdx = stack.pop()
<topIdx, i>匹配成功
// 问题1: 如果这里栈为空，怎么办？
// 问题3: 如果这里栈非空，怎么办？
else:
// 问题2:遇到栈为空，无法弹怎么办？
else:
stack.push(i)
|
问题 1：弹栈之后的空栈
当我们需要为红框中的右括号 s[i] 进行匹配，并且弹栈之后，栈为空。那么我们可以得到一个结论 1：
此时，整个字符串从开头到当前位置是一个合法有效的字符串。
但是，这个结论 1会遇到下面这种坑。
例 1：给定的字符串是 “)))()"，当我们处理最后一个字符 s[4] 的时候，弹栈之后，栈肯定为空。但是，我们不能认为 [0, 4] 是一个有效的合法子串。
那么，是不是结论 1 不对呢？其实不尽然，只是我们有可能需要重新定义字符串的开头。
问题 2：空栈无法弹
假设，字符串是 s = “))))"。如果按照结论 1 来进行操作，每个位置都会得到空栈，我们可以得到每个位置的最长合法子串，如下图所示：
显然，这样处理是不合适的。那么问题出在哪里呢？
在特点 2 中，我们证明了合法字符串必须满足连续性，那么当我们找到一个右括号，但是找不到任何左括号与之配对的时候，就可以扔掉左边的字符了。
这也就意味着，在找到一个字符 s[i]，找不到匹配的时候，需要切掉 [0,i] 这部分子串。
当然，为了处理方便，我们不会真正去切这个子串，而是重新定义一个 start 变量来表示新的字符串的起始位置。
在切掉 [0, i] 这部分子串的时候，就可以有如下操作：
当 s[i] 为右括号，栈为空的时候，设置新的字符串的起始点 start = i + 1。
打上这个补丁之后，字符串 s = “))))” 就可以正确处理了。到此时，我们发现，并不是结论 1 不对，而是结论 1 中的“开头 start”在遇到空栈无法弹的时候，需要重新定义。
问题 3：弹栈后非空
如果弹栈之后，栈非空，那么必然是遇到了 s = “((()()(）“这种字符串。当我们处理最后一个字符（会将 6 弹栈），如下图所示：
但是，弹栈之后，栈顶元素就变成了 1。我们发现 (1, 7] 这段区间都是一个有效的合法区间。因此，弹栈之后，栈非空的情况：区间（存留的栈顶元素，i] 是一个合法的子串。
处理好问题 1、问题 2、问题 3 之后，我们就可以写出如下代码了（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public int longestValidParentheses(String s) {
// 拿到字符串的长度
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
}
Stack<Integer> st = new Stack<>();
// 最长的有效长度
int ans = 0;
int start = 0;
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
// 如果从[start, i]这个区间里面
// 右括号已经可以匹配掉所有的左括号了
if (st.isEmpty()) {
// 问题2:更新新字符串的开头
start = i + 1;
} else {
st.pop();
// 注意问题1，3在这里统一处理
final int base =
st.isEmpty() ? start : st.peek() + 1;
ans = Math.max(ans, i - base + 1);
}
} else { /* 如果字符是左括号 */
st.push(i);
}
} // end for
return ans;
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(N)。
前面我们介绍的算法最优情况下，时间复杂度都是 O(N)，但是空间复杂度也都为 O(N)。有没有可能优化一下空间复杂度呢？
特点 5：合法字符串的性质
如果优化空间复杂度，我们需要再挖掘一下合法子串的性质。对于任意一个合法子串，都必然满足以下两个性质。
合法性质 1：对于任意一个合法子串，当我们从左往右遍历这个子串的时候，左括号的数目永远 >= 右括号的数目。
合法性质 2：对于任意一个合法子串，当我们从右往左遍历这个子串的时候，右括号的数目永远 >= 左括号的数目。
那么，我们是否可以反推呢？
1） 利用合法性质 1，我们从左往右遍历，找到一个最长的区间，使其总是满足左括号的数目 >= 右括号的数目。那么当左括号数目 == 右括号数目，此时就可以得到一个最长的合法子串，我们记为maxEquLength1。
2）利用合法性质 2，我们从右往左遍历，找到一个最长的区间，使其总是满足右括号的数目 >= 左括号的数目。那么当左括号数目 == 右括号数目，此时就可以得到一个最长的合法子串，我们记为 maxEquLength2。
最后，再取这两者的最大值：max(maxEquLength1, maxEquLength2)。
那么，有没有可能只从左向右遍历一次呢？答案是不行！
原因是：如果只利用合法性质 1 从左向右遍历，那么无法处理字符串 s = “(()"；如果只利用合法性质 2 从右向左遍历，那么无法处理字符串 s = “())"。
结合以上分析，我们可以写出如下代码（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
}
// 合法子串性质1
// 1. 最长
// 2. 在任何时间，左括号数量 >= 右括号数量
// 左括号的数量
int leftBraceNumber = 0;
// 右括号的数量
int rightBraceNumber = 0;
// 第一次扫描的区间的长度
int maxEquLength1 = 0;
for (int i = 0; i < N; i++) {
// 取出这个字符
final char c = s.charAt(i);
leftBraceNumber += c == '(' ? 1 : 0;
rightBraceNumber += c == ')' ? 1 : 0;
// 我们总是想让括号的数目 >= 右括号的数目
// 如果不成立了！
// 我们去掉左边的任何一部分，都不会合得条件再次成立
// 所以直接需要让两个计数器归0
if (rightBraceNumber > leftBraceNumber) {
leftBraceNumber = 0;
rightBraceNumber = 0;
}
// 如果计数相等的时候
if (leftBraceNumber == rightBraceNumber) {
maxEquLength1 =
Math.max(maxEquLength1,
leftBraceNumber + rightBraceNumber);
}
} // end for
// 合法子串性质2
// 1. 最长
// 2. 在任何时间，左括号数量 <= 右括号数量
// 如果不利用 性质2，那么无法处理(()这种情况
int maxEquLength2 = 0;
leftBraceNumber = 0;
rightBraceNumber = 0;
for (int i = N - 1; i >= 0; i--) {
// 取出字符
final char c = s.charAt(i);
leftBraceNumber += c == '(' ? 1 : 0;
rightBraceNumber += c == ')' ? 1 : 0;
if (leftBraceNumber > rightBraceNumber) {
leftBraceNumber = 0;
rightBraceNumber = 0;
}
if (leftBraceNumber == rightBraceNumber) {
maxEquLength2 =
Math.max(maxEquLength2,
leftBraceNumber + rightBraceNumber);
}
} // end for
// 最后取两者中最长的
return Math.max(maxEquLength1, maxEquLength2);
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(1)。
在这里，我们抓住了合法字符串的性质 1 和性质 2，然后利用贪心算法在 O(1) 空间内解决了这个题目。在做题的时候，如果挖掘出题目的更多信息，再匹配到合适的算法，就能够帮助我们巧妙地破题。
总结
在本讲，我们通过一个括号匹配的题目，深入挖掘了题目的特点，然后再使用上各种算法与数据结构，得到了各种巧妙的解法。我将本讲的内容整理成了思维导图，帮助你总结思路：
思考题
最后，我还给你留了一个思考题。
思考题：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入：n = 3
输出：[”((()))”,”(()())”,”(())()”,”()(())”,"()()()"]
代码：Java/C++/Python
你可以自己尝试求解这道题目，把答案写在留言区，我们一起讨论。关于这道括号的题目就介绍到这里。接下来，下一讲介绍“21 | 安排会议室：如何利用多种方法安排会议室？”，让我们继续前进。
-– ### 精选评论 ##### **阳： > 思考题中暴力求解的思路是先枚举所有括号生成结果，再用有效括号长度等于2n的判断条件得到所有符合的结果。进一步想的话，实际上在枚举的过程中可以根据合法串性质来判断并同时得到结果