LeetCode 32. 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
class Solution: def longestValidParentheses(self, s: str) -> int: left, right, maxlen = 0, 0, 0 # left 代表左括号的个数, right代表右括号的个数 # 从左到右遍历 for char in s: if char == '(': left += 1 else: right += 1 if left == right: # 是合理的 maxlen = max(maxlen, 2 * right) elif right > left: # 不合理, 且最后遍历的是右括号, 不可能是后面子串的开始, 所以两者直接设置为0 left, right = 0, 0 # 从由到左遍历 因为如果是 (()的情况从左边是得不到最大长度的 left, right = 0, 0 for char in s[::-1]: if char == ')': right += 1 else: left += 1 if left == right: maxlen = max(maxlen, 2 * left) elif right < left: left, right = 0, 0 return maxlen遍历每个字符后, 统计一个左括号和右括号的个数, 只要右括号大于左括号的个数, 那就是不合理的, 并且刚遍历的一个字符肯定是右括号, 所以直接将他们的个数设置为0, 重新开始统计
这样得到的可能是(((((), 但是由于左括号数量大于右括号的数量, 所以我们错误地认为它是合理的, 这时我们需要倒序遍历一遍即可
