golang力扣leetcode 32.最长有效括号

32.最长有效括号

32.最长有效括号

题解

题目：求匹配括号的最长长度

思路一 栈

遍历字符串
1.如果是(,则入栈
2.如果是),如果栈空，说明这个右括号是多于的，将对应的mark置1
		 如果栈不空，则弹出栈顶
3.遍历栈，如果栈里还有没有被弹出的(,将对应的mark置1
4.计算连续0的长度，即计算最长可用长度

思路二 dp
dp[i]表示以s[i]字符结尾的最长有效长度

如果s[i]== (

• 左括号不能与前面的元素匹配，所以dp[i]=0

如果s[i]== )

• 如果s[i-1]== (
• • 说明构成了（）的形式，那么有效长度增加2，即dp[i]=dp[i-2]+2
• • 
• 如果s[i-1]== )
• • 说明构成了xxx ))的形式，这个时候想要形成(())的形式，需要要求s[i-1]的位置是匹配的，如果s[i-1]不匹配，s[i]则不能与前面的(匹配
• • 所以判断s[ i-1-dp[i-1] ] 是否为(
• • • 如果s[ i-1-dp[i-1] ]== ( ,说明 i-1-dp[i-1]的左括号和i的右括号匹配，则dp[i]=dp[i-2]+2
• • • 但是这里只是考虑了(())的情况，如果是()(())的情况呢？前面的()的长度我们也要加上,所以dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]]
• • • 

综上所述，dp的状态转移方程为

dp[i] = dp[i-2] + 2 //xxxx()

dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]] //()(())

思路三 贪心 遍历两次

我们知道有效括号代表这能够匹配，那么

1. 遇到(,left++ 遇到) right++
2. 如果left=right,说明匹配成功
3. 如果left<right，这个情况的前面相等时的长度已经记录过了，直接将left和right置为0
4. 但是(()这种情况，将没有答案
5. 这个时候倒着再遍历一遍，将第三步改为如果left>right即可

代码

func longestValidParentheses(s string) int {
	mark := make([]int, len(s))
	stack := make([]int, 0)
	for i, ch := range s {
		if ch == '(' { //如果是(，则入栈
			stack = append(stack, i)
		}
		if ch == ')' { //如果是）
			if len(stack) == 0 { //如果是多余的)，说明该位置不可用
				mark[i] = 1
			} else {
				stack = stack[:len(stack)-1] //不是多余的，则弹出一个(
			}
		}
	}
	for _, idx := range stack { //还在栈里面没有被匹配的(,都不可用
		mark[idx] = 1
	}
	ans, temp := 0, 0
	for i := 0; i < len(mark); i++ { //计算最长可用长度
		if mark[i] == 1 {
			temp = 0
		} else {
			temp++
			ans = max(ans, temp)
		}
	}
	return ans
}
func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

func longestValidParentheses(s string) int {
	ans := 0
	dp := make([]int, len(s))
	for i := 1; i < len(s); i++ {
		ch := s[i]
		if ch == '(' {
			dp[i] = 0
		} else if ch == ')' {
			if s[i-1] == '(' {
				if i-2 >= 0 {
					dp[i] = dp[i-2] + 2 //xxxx()
				} else {
					dp[i] = 2 //()
				}
			} else if s[i-1] == ')' {
				if i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '(' {
					if i-2-dp[i-1] >= 0 {
						dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]] //()(())
					} else {
						dp[i] = dp[i-1] + 2 //(())
					}
				}
			}
		}
		ans = max(ans, dp[i])
	}
	return ans
}
func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

func longestValidParentheses(s string) int {
	left, right := 0, 0
	ans := 0
	for _, v := range s {
		if v == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			ans = max(ans, left+right)
		}
		if right > left {
			left, right = 0, 0
		}
	}
	left, right = 0, 0
	for i := len(s) - 1; i >= 0; i-- {
		v := s[i]
		if v == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			ans = max(ans, left+right)
		}
		if left > right {
			left, right = 0, 0
		}
	}
	return ans
}
func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}