#P4097. 最长有效括号
-
ID: 2334
Tried: 75
Accepted: 24
Difficulty: 5
最长有效括号
题目描述
给定一个只包含 ( 和 ) 的字符串 s，找出最长的有效（格式正确且连续）括号子串的长度。
输入描述
输入包含一个字符串 s（0≤∣s∣≤3×104），仅包含 ( 和 )。
输出描述
输出一行，表示最长的有效括号子串的长度。
样例输入 1
(()
样例输出 1
2
样例输入 2
)()())
样例输出 2
4
样例输入 3
()
样例输出 3
2
提示
s只包含(和)。- 结果是
s中最长的有效括号子串的长度。
解题思路
对于 最长有效括号子串 问题，常见的两种方法是：
- 动态规划（DP）
- 栈（Stack）
方法 1：动态规划（DP）
思路
- 定义
dp[i]表示 以i结尾的 最长有效括号子串的长度。 - 只有
s[i] == ')'时，才可能形成有效括号：- 如果
s[i-1] == '('dp[i] = dp[i-2] + 2
- 如果
s[i-1] == ')'，且s[i - dp[i-1] - 1] == '('dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2
- 如果
- 遍历字符串，计算
dp[i]，最终返回dp数组的最大值。
时间 & 空间复杂度
- 时间复杂度： O(n)
- 空间复杂度： O(n)
方法 2：使用栈（Stack）
思路
- 使用 栈 记录括号的索引，保证匹配时可以弹出并计算长度：
- 如果
s[i] == '('，入栈。 - 如果
s[i] == ')'：- 如果栈非空，弹出栈顶元素，计算当前有效长度
i - stack[-1]。 - 如果栈为空，说明当前位置无匹配，更新
start = i + 1。
- 如果栈非空，弹出栈顶元素，计算当前有效长度
- 如果
- 取遍历过程中最大长度作为答案。
时间 & 空间复杂度
- 时间复杂度： O(n)
- 空间复杂度： O(n)
Python 代码
方法 1：动态规划
import sys
def longest_valid_parentheses_dp(s):
n = len(s)
if n == 0:
return 0
dp = [0] * n # dp[i] 表示以 s[i] 结尾的最长有效括号长度
max_length = 0 # 记录最大长度
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
dp[i] = (dp[i - 2] if i >= 2 else 0) + 2 # 形如 "()" 的情况
elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
max_length = max(max_length, dp[i])
return max_length
def main():
s = sys.stdin.readline().strip()
print(longest_valid_parentheses_dp(s))
if __name__ == "__main__":
main()
方法 2：使用栈
import sys
def longest_valid_parentheses_stack(s):
stack = [-1] # 记录索引，初始值为 -1
max_length = 0 # 记录最长有效括号长度
for i, char in enumerate(s):
if char == '(':
stack.append(i) # 左括号入栈
else:
stack.pop() # 右括号尝试匹配
if stack:
max_length = max(max_length, i - stack[-1]) # 计算有效长度
else:
stack.append(i) # 记录无效起点
return max_length
def main():
s = sys.stdin.readline().strip()
print(longest_valid_parentheses_stack(s))
if __name__ == "__main__":
main()
Java 代码
方法 1：动态规划
import java.util.*;
public class Main {
public static int longestValidParenthesesDP(String s) {
int n = s.length();
if (n == 0) return 0;
int[] dp = new int[n]; // dp[i] 表示以 s[i] 结尾的最长有效括号长度
int maxLength = 0; // 记录最大长度
for (int i = 1; i < n; 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;
}
maxLength = Math.max(maxLength, dp[i]);
}
}
return maxLength;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
System.out.println(longestValidParenthesesDP(s));
sc.close();
}
}
方法 2：使用栈
import java.util.*;
public class Main {
public static int longestValidParenthesesStack(String s) {
Stack<Integer> stack = new Stack<>();
stack.push(-1); // 记录索引，初始值 -1
int maxLength = 0; // 记录最长长度
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i); // 左括号入栈
} else {
stack.pop(); // 右括号尝试匹配
if (!stack.isEmpty()) {
maxLength = Math.max(maxLength, i - stack.peek()); // 计算有效长度
} else {
stack.push(i); // 记录无效起点
}
}
}
return maxLength;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
System.out.println(longestValidParenthesesStack(s));
sc.close();
}
}
C++ 代码
方法 1：动态规划
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int longestValidParenthesesDP(const string& s) {
int n = s.size();
vector<int> dp(n, 0); // dp[i] 记录以 s[i] 结尾的最长有效括号长度
int max_length = 0;
for (int i = 1; i < n; i++) {
if (s[i] == ')') {
if (s[i - 1] == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
max_length = max(max_length, dp[i]);
}
}
return max_length;
}
int main() {
string s;
cin >> s;
cout << longestValidParenthesesDP(s) << endl;
return 0;
}
方法 2：使用栈
#include <iostream>
#include <stack>
using namespace std;
int longestValidParenthesesStack(string s) {
stack<int> st;
st.push(-1);
int max_length = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
st.push(i);
} else {
st.pop();
if (!st.empty()) {
max_length = max(max_length, i - st.top());
} else {
st.push(i);
}
}
}
return max_length;
}
int main() {
string s;
cin >> s;
cout << longestValidParenthesesStack(s) << endl;
return 0;
}