32. 最长有效括号
查看题目困难
字符串
中频
解法一：动态规划
时间复杂度： | 空间复杂度： | 推荐使用
动画演示
准备就绪 - 输入括号字符串，然后点击开始
代码实现
// Java 实现 - 动态规划
class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
}时间复杂度：
空间复杂度：
解法二：栈
时间复杂度： | 空间复杂度：
动画演示
准备就绪 - 输入括号字符串，然后点击开始
代码实现
// Java 实现 - 栈
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
}时间复杂度：
空间复杂度：
解法三：双指针
时间复杂度： | 空间复杂度：
动画演示
准备就绪 - 输入括号字符串，然后点击开始
代码实现
// Java 实现 - 双指针
class Solution {
public int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxlength;
}
}时间复杂度：
空间复杂度：