刷题使我快乐，满脸开心.jpg

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

题目

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

思路

双向遍历法

一开始看到题目，就是想着统计左右个数进行比较，但是写着写着发现有个问题，那就是如果左括号一直大于右括号，就一直无法去更新最大值。
然后突然间意识到，如果把字符串‘翻过来’从左往右看，那么左括号一直大于右括号的情况就不是问题了！
所以就左右各走一遍！这样就能统计完整了！

栈方法

栈方法是解完之后想了些思路都没能成功，还以为会特别复杂，但是看题解时，才发现跟自己原本的思路，主要是差在了初始栈压入-1。
这个设计非常巧妙了，因为之前自己的思路在遇到右括号时，根据栈空与非空、栈内元素构成等原因导致复杂度飙升，没能解出来。整理下题解的思路：

• 开始先压入一个-1
• 左括号时直接压入下标
• 右括号时无论如何先弹出一个下标，后面只需要判断栈是否为空即可
  • 如果是空的，说明右括号已经多于左括号，把初始值都弹出了，其实也就是说后续的字符不可能跟前面的串联起来组成更长的子串，这时压入当前下标，这也就是下一个可能合法子串的起点（确切说是起点之前的下标）
  • 如果不是空的，说明之前有过左括号压入，那么在现在的栈顶元素之后的子串就是一个合法的子串，可以尝试去更新最长子串的值。

动态规划

官方题解中海油动态规划的方法，我看题解之前没有这方面的思路就不说了，大家感兴趣可以自己去看看~

代码

双向遍历法

func longestValidParentheses(s string) int {
	sBytes := []byte(s)
	left, right, maxLen := 0, 0, 0
    // 从左往右寻找合法子串
	for _, v := range sBytes {
		if v == '(' {
			left++
		} else {
			right++
		}
        // 相等了也就是一个合法子串，尝试更新最大长度
		if left == right && 2*left > maxLen {
			maxLen = 2 * left
		} else if right > left {
            // 右大于左，则后面也不可能是合法的，重新计数
			left, right = 0, 0
		}
	}
    // 从左往右无法计算左一直大于右的情况，所以从右往左再来一遍
	left, right = 0, 0
	for i := len(sBytes) - 1; i > 0; i-- {
		if sBytes[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right && 2*left > maxLen {
			maxLen = 2 * left
		} else if right < left {
            // 这个时候左大于右就是非法的了
			left, right = 0, 0
		}
	}
	return maxLen
}

栈方法

func longestValidParentheses(s string) int {
	stack := make([]int, 0)
    // 初始压入-1
	stack = append(stack, -1)
	maxLen := 0
	for i, byteItem := range []byte(s) {
        // 左括号直接入栈
		if byteItem == '(' {
			stack = append(stack, i)
		} else {
            // 右括号直接出栈一个
			stack = stack[:len(stack)-1]
            // 说明子串已经被截断
			if len(stack) == 0 {
				stack = append(stack, i)
			} else {
                // 说明子串还在持续合法中
				if i-stack[len(stack)-1] > maxLen {
					maxLen = i - stack[len(stack)-1]
				}
			}
		}
	}
	return maxLen
}