最长有效括号
Wallace Xu 2020-10-13 栈动态规划
我们遇到括号匹配问题往往会想到使用栈来解决，这一题的栈解法却有一些特殊，此外还有动态规划解法也可以用来解决。
# LeetCode 32. 最长有效括号 (opens new window)
# 题目描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
# 示例
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
1
2
3
4
5
6
7
2
3
4
5
6
7
# 解题思路
思路1：栈。一开始我尝试使用额外的两个整形变量和一个布尔变量来标记当前是否还在处理合法并连续的括号对与已知的括号对的左右边界。并通过更新边界来寻找最长的子串的长度：
public int longestValidParentheses(String s) {
if (s == null || s.length() <= 1) return 0;
int n = s.length(), maxLength = 0, leftBoundary = n, rightBoundary = 0;
boolean stillValid = true;
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') { //如果是左括号就将其下标入栈
stack.push(i);
} else { //如果是右括号就尝试从栈顶找距离其最近的左括号，需要根据栈顶元素进一步判断
if (stack.isEmpty()) { //如果栈顶没有元素说明没有与之匹配的左括号，将状态置为无效
stillValid = false;
} else { //如果栈顶有元素那么一定是与之匹配的左括号
int leftIndex = stack.pop();
if (stillValid) { //如果上一次状态仍然是有效，更新到目前为止有效的子串的左右边界
leftBoundary = Math.min(leftBoundary, leftIndex);
rightBoundary = Math.max(rightBoundary, i);
} else { //如果上一次状态是无效，那么这一次发现的左右括号对就是新开始的有效子串的左右边界
leftBoundary = leftIndex;
rightBoundary = i;
stillValid = true;
}
//进一步更新最长长度
maxLength = Math.max(maxLength, rightBoundary - leftBoundary + 1);
}
}
}
return maxLength;
}
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
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
但是这种方式存在漏洞，仅根据当前位置的字符来选择行为，对于“)”并不能验证前面一定有一个左括号能对应组成一个连续且合法的括号对。看了下官方题解的思路很巧妙：
“始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」”。
public int longestValidParentheses(String s) {
if (s == null || s.length() <= 1) return 0;
int n = s.length(), maxLength = 0;
Deque<Integer> stack = new LinkedList<>();
stack.push(-1);
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') { //如果是左括号就将其下标入栈
stack.push(i);
} else { //如果是右括号就尝试从栈顶弹出距离其最近的左括号
stack.pop();
//如果弹出能匹配的左括号后栈中还有元素则该元素表示前一个弹出的左括号左边的那个字符
//（左边的那个字符可能是左括号也可能是最后一次没有被匹配的右括号）
if (!stack.isEmpty()) {
maxLength = Math.max(maxLength, i - stack.peek());
} else { //否则栈底表示最后一次没有被匹配的右括号下标，我们知道当前位置i上的右括号是没有匹配的的
stack.push(i);
}
}
}
return maxLength;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
思路2：动态规划。使用dp[i]表示以第个位置结尾的子串所能表示的最长有效括号对的长度。
public int longestValidParentheses(String s) {
if (s == null || s.length() <= 1) return 0;
int n = s.length(), max = 0;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
//如果当前位置是左括号那么必然不可能是一个完整括号对的结尾，默认为0不用处理
if (s.charAt(i) == ')')
//如果前一个位置是左括号那么直接组成一个括号对，长度在dp[i - 2]（如果存在的话）的基础上加2即可
if (s.charAt(i - 1) == '(')
dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
//否则前一个位置是右括号就需要根据dp[i - 1]找到前面对应位置X
//如果前面对应位置X有和第i个位置匹配的左括号
else if (i - 1 - dp[i - 1] >= 0 && s.charAt(i - 1 - dp[i - 1]) == '(')
//那么在dp[i] = dp[i - 1] + 2的基础上还要记得加上X左边可能的连续括号对长度
dp[i] = dp[i - 1] + 2 + (i - 2 - dp[i - 1] >= 0 ? dp[i - 2 - dp[i - 1]] : 0);
//否则前面没法找到一个合适的左括号与当前第i个位置的')'组成合法的括号对，那么dp[i]默认为0
max = Math.max(max, dp[i]);
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21