Leetcode32最长有效括号

32最长有效括号

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

执行用时：56 ms
内存消耗：13.8 MB

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        """
        思路：有效括号价于下面3个条件:
            从左往右看，每个地方左括号数量大于等于右括号
            从右往左看，每个地方右括号数量大于等于左括号
            左右括号数量相等
        """
        left = 0
        right = 0
        maxLen = 0
        for i in range(len(s)):
            if s[i] == '(':
                left += 1
            elif s[i] == ')':
                right += 1
            if right > left:
                left = 0
                right = 0
            elif left == right:
                maxLen = max(maxLen, left*2)
        left = 0
        right = 0
        for i in range(-1, -len(s)-1, -1):
            if s[i] == '(':
                left += 1
            elif s[i] == ')':
                right += 1
            if left > right:
                left = 0
                right = 0
            elif left == right:
                maxLen = max(maxLen, left*2)
        return maxLen