class Solution {
public:
int longestValidParentheses(string s) {
}
};
32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
0 <= s.length <= 3 * 104s[i] 为 '(' 或 ')'相似题目
原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 17.2 MB, 提交时间: 2024-04-23 14:35:35
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = []
res = 0
for i in range(len(s)):
if not stack or s[i] == '(' or s[stack[-1]] == ')':
stack.append(i)
else:
stack.pop()
res = max(res, i - (stack[-1] if stack else - 1))
return res
java 解法, 执行用时: 1 ms, 内存消耗: 41.2 MB, 提交时间: 2024-04-23 14:35:10
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;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 17.3 MB, 提交时间: 2024-04-23 14:34:53
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack=[]
maxL=0
n=len(s)
tmp=[0]*n #标记数组
cur=0
for i in range(n):
if s[i]=='(':
stack.append(i)
else:
if stack:
j=stack.pop()
if s[j]=='(':
tmp[i],tmp[j]=1,1 #匹配成功标记
for num in tmp: #计算连续1出现的最大次数
if num:
cur+=num
else: #遇到0时中断，进行对比，并重置
maxL=max(cur,maxL)
cur=0
maxL=max(cur,maxL) #最后一次统计可能未终断，需多做一次对比
return maxL
cpp 解法, 执行用时: 3 ms, 内存消耗: 8.6 MB, 提交时间: 2024-04-23 14:33:58
class Solution {
public:
int longestValidParentheses(string s) {
int maxans = 0;
stack<int> stk;
stk.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
stk.push(i);
} else {
stk.pop();
if (stk.empty()) {
stk.push(i);
} else {
maxans = max(maxans, i - stk.top());
}
}
}
return maxans;
}
// dp
int longestValidParentheses2(string s) {
int maxans = 0, n = s.length();
vector<int> dp(n, 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;
}
maxans = max(maxans, dp[i]);
}
}
return maxans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 41.6 MB, 提交时间: 2024-04-23 14:33:22
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;
}
// 基于栈
public int longestValidParentheses2(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;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2022-08-10 16:22:54
func longestValidParentheses(s string) int {
left, right, maxLength := 0, 0, 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
left++
} else {
right++
}
if left == right {
maxLength = max(maxLength, 2 * right)
} else if right > left {
left, right = 0, 0
}
}
left, right = 0, 0
for i := len(s) - 1; i >= 0; i-- {
if s[i] == '(' {
left++
} else {
right++
}
if left == right {
maxLength = max(maxLength, 2 * left)
} else if left > right {
left, right = 0, 0
}
}
return maxLength
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
golang 解法, 执行用时: 0 ms, 内存消耗: 3.3 MB, 提交时间: 2022-08-10 16:22:42
func longestValidParentheses(s string) int {
maxAns := 0
stack := []int{}
stack = append(stack, -1)
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack)-1]
if len(stack) == 0 {
stack = append(stack, i)
} else {
maxAns = max(maxAns, i - stack[len(stack)-1])
}
}
}
return maxAns
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2022-08-10 16:22:12
func longestValidParentheses(s string) int {
maxAns := 0
dp := make([]int, len(s))
for i := 1; i < len(s); i++ {
if s[i] == ')' {
if s[i-1] == '(' {
if i >= 2 {
dp[i] = dp[i - 2] + 2
} else {
dp[i] = 2
}
} else if i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(' {
if i - dp[i - 1] >= 2 {
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
} else {
dp[i] = dp[i - 1] + 2
}
}
maxAns = max(maxAns, dp[i])
}
}
return maxAns
}
func max(x, y int) int {
if x > y {
return x
}
return y
}