最长有效括号 - 动态规划
func longestValidParentheses(s string) int {
n := len(s)
ans := 0
// dp[i]: 以 i 为结尾的最长有效括号的长度
// 如果 s[i] == '('，则 dp[i] = 0，因为以 '(' 结尾不会是有效括号
dp := make([]int, n)
for i := 1; i < n; i++ {
if s[i] != ')' {
continue
}
if s[i - 1] == '(' { // ...()
if i - 2 < 0 {
dp[i] = 2
} else {
dp[i] = dp[i - 2] + 2
}
} else if i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(' { // ...((...))
if i - dp[i - 1] - 2 < 0 {
dp[i] = dp[i - 1] + 2
} else {
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
}
}
ans = max(ans, dp[i])
}
return ans
}最长有效括号 - 栈
func longestValidParentheses(s string) int {
n := len(s)
ans := 0
// 栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
stack := []int{ -1 }
for i := 0; i < n; i++ {
if s[i] == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack) - 1]
if len(stack) == 0 {
// 说明当前的右括号为没有被匹配的右括号
// 将其下标放入栈中来更新「最后一个没有被匹配的右括号的下标」
stack = append(stack, i)
} else {
// 当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
ans = max(ans, i - stack[len(stack) - 1])
}
}
}
return ans
}最长有效括号 - 贪心
利用两个计数器记录左右括号的数量，先从左到右遍历字符串
这样贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (()
解决的方法也很简单，只需要从右往左遍历用类似的方法计算即可
func longestValidParentheses(s string) int {
n := len(s)
ans := 0
left, right := 0, 0 // 记录遇到 '(' 和 ')' 的数量
for i := 0; i < n; i++ {
if s[i] == '(' {
left++
} else {
right++
}
if right > left {
left = 0
right = 0
} else if left == right {
ans = max(ans, left + right)
}
}
left, right = 0, 0
for i := n - 1; i >= 0; i-- {
if s[i] == '(' {
left++
} else {
right++
}
if left > right {
left = 0
right = 0
} else if left == right {
ans = max(ans, left + right)
}
}
return ans
}