Skip to main content

32. Longest Valid Parentheses

分析

  为什么要用栈?
处理未能匹配的元素,即除了 栈顶为 '(' 当前为 ')‘ 的其他情况

最长有效的统计,要利用边界,并不断改变边界

那些未能匹配的
- 要么作为 '(' 等待着
- 要么成为边界

看的一些题解一步到位了,省去了一些中间思考,下面逐渐去除不必要的空间消耗

题解

stack 无优化 最好理解

type T struct {
V rune
Index int
}

func longestValidParentheses(s string) int {
stack := []T{T{')', -1}}

ans := 0

for i, v := range s {
// 匹配的情况
if len(stack) > 1 && stack[len(stack)-1].V == '(' && v == ')' {
stack = stack[:len(stack)-1]
lastIndex := stack[len(stack)-1].Index
ans = max(ans, i-lastIndex)
} else {
stack = append(stack, T{v, i})
}
}

return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

减少不必要的 stack 存入

type T struct {
V rune
Index int
}

func longestValidParentheses(s string) int {
stack := []T{T{')', -1}}

ans := 0

for i, v := range s {
// 匹配的情况
if len(stack) > 1 && stack[len(stack)-1].V == '(' && v == ')' {
stack = stack[:len(stack)-1]
lastIndex := stack[len(stack)-1].Index
ans = max(ans, i-lastIndex)
} else {
if len(stack) == 1 && v == ')' {
// 需要重新确立边界了
stack = []T{T{')', i}}
continue
}
stack = append(stack, T{v, i})
}
}

return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

省去结构类型的辅助理解

func longestValidParentheses(s string) int {
stack := []int{-1}

ans := 0

for i, v := range s {
// 匹配的情况
if len(stack) > 1 && v == ')' {
stack = stack[:len(stack)-1]
lastIndex := stack[len(stack)-1]
ans = max(ans, i-lastIndex)
} else {
if len(stack) == 1 && v == ')' {
// 需要重新确立边界了
stack = []int{i}
continue
}
stack = append(stack, i)
}
}

return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}