Longest Valid Parentheses
描述
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
题解
package algorithms
//Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
//
//For "(()", the longest valid parentheses substring is "()", which has length = 2.
//
//Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
func longestValidParentheses(s string) int {
var longest, substringStart int
stk := make([]int, len(s))
top := -1
for i := 0; i < len(s); i++ {
if s[i] == '(' { // '('入栈
top++
stk[top] = i
} else { // s[i] == ')' 两种情况
if top == -1 { // 1. 栈为空,substringStart为下一个字符
substringStart = i + 1
} else { // 2. 栈不为空,两种情况
top-- // '('出栈
var length int
if top == -1 { // (1) 栈为空,substring有效,length+1
length = i - substringStart + 1
} else { // (2) 栈不为空,取有效部分substring长度
length = i - stk[top]
}
if length > longest {
longest = length
}
}
}
}
return longest
}
func longestValidParenthesesBest(s string) int {
l := 0
if len(s) >= 1 {
i, stack := 0, make([]int, len(s)+1)
stack[0] = -1
for si := 0; si < len(s); si++ {
if s[si] == '(' {
i++ // push
stack[i] = si
} else {
i-- // pop
if i < 0 {
i = 0 // push
stack[i] = si
} else if tmp := si - stack[i]; tmp > l {
l = tmp
}
}
}
}
return l
}