文章目录

• 32. 最长有效括号：
• • 样例 1：
  • 样例 2：
  • 样例 3：
  • 提示：
• 分析：
• 题解：
• • rust
  • go
  • c++
  • c
  • python
  • java

32. 最长有效括号：

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

样例 1：

输入：s = "(()"输出：2解释：最长有效括号子串是 "()"

样例 2：

输入：s = ")()())"输出：4解释：最长有效括号子串是 "()()"

样例 3：

输入：s = ""输出：0

提示：

• 0 <= s.length <= 3 * 10⁴
• s[i] 为 '(' 或 ')'

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 只有小括号，判断有效是关键。
• 从左向右看，左括号数始终大于等于右括号数，并且最终左右括号数相等。
• 从右向左看，右括号数始终大于等于左括号数，并且最终左右括号数相等。

题解：

rust

impl Solution {pub fn longest_valid_parentheses(s: String) -> i32 {let (mut left, mut right, mut maxlength) = (0, 0, 0);s.as_bytes().iter().for_each(|&b| {if b == b'(' {left += 1;} else {right += 1;}if left == right {maxlength = maxlength.max(2 * right);} else if right > left {left = 0;right = 0;}});left = 0;right = 0;s.as_bytes().iter().rev().for_each(|&b| {if b == b'(' {left += 1;} else {right += 1;}if left == right {maxlength = maxlength.max(2 * left);} else if left > right {left = 0;right = 0;}});return maxlength;}
}

go

func longestValidParentheses(s string) int {max := func(x, y int) int {if x > y {return x}return y}left, right, maxLength := 0, 0, 0for 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, 0for 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
}

c++

class Solution {
public:int longestValidParentheses(string s) {int left = 0, right = 0, maxlength = 0;for (int i = 0; i < s.length(); ++i) {if (s[i] == '(') {left++;} else {right++;}if (left == right) {maxlength = max(maxlength, 2 * right);} else if (right > left) {left = right = 0;}}left = right = 0;for (int i = (int) s.length() - 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;}}return maxlength;}
};

c

int longestValidParentheses(char * s){const int len = strlen(s);int left = 0, right = 0, maxlength = 0;for (int i = 0; i < len; ++i) {if (s[i] == '(') {left++;} else {right++;}if (left == right) {maxlength = fmax(maxlength, 2 * right);} else if (right > left) {left = right = 0;}}left = right = 0;for (int i = len - 1; i >= 0; --i) {if (s[i] == '(') {left++;} else {right++;}if (left == right) {maxlength = fmax(maxlength, 2 * left);} else if (left > right) {left = right = 0;}}return maxlength;
}

python

class Solution:def longestValidParentheses(self, s: str) -> int:left, right, max_length = 0, 0, 0for i in range(len(s)):if s[i] == '(':left += 1else:right += 1if left == right:max_length = max(max_length, 2 * right)elif right > left:left, right = 0, 0left, right = 0, 0for i in range(len(s) - 1, -1, -1):if s[i] == '(':left += 1else:right += 1if left == right:max_length = max(max_length, 2 * left)elif left > right:left, right = 0, 0return max_length

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;}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~