leetcode [32] 最长有效括号

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

示例 1:

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

示例 2:

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

思路来自题解

解法1：

来回扫描两次，第一次往右扫描，对左右括号进行计数，如果相等表示有效，记录最大值，如果右括号大于左括号，那么左右括号重新计数。第二次往左扫描，相等记录，如果左括号大于右括号，重新计数。

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

        left = right = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '(':
                left += 1
            else:
                right += 1
            if left == right:
                maxlen = max(maxlen, left + right)
            elif left > right:
                left = right = 0
        return maxlen

解法2：使用栈，细节较多。先加入-1。左括号入栈位置，右括号出栈，出栈后如果为空，加入当前的位置，否则记录和栈内元素最大差值。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) == 0:
            return 0
        stack = []
        maxlen = 0
        stack.append(-1)
        for i, ss in enumerate(s):
            if ss == '(':
                stack.append(i)
            else:
                stack.pop()
                if len(stack) == 0:
                    stack.append(i)
                else:
                    maxlen = max(i - stack[-1], maxlen)
        return maxlen

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) == 0: return 0
        stack = [-1]
        ans = 0
        for i, ss in enumerate(s):
            if ss == '(':
                stack.append(i)
            else:
                if len(stack) > 1 and s[stack[-1]] == '(':
                    stack.pop()
                    ans = max(ans, i - stack[-1])
                else:
                    stack.append(i)
        return ans