32. Longest Valid Parentheses
Medium
Given a string containing just the characters
'('
and ')'
, return the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = "(()"
Output:
2
Explanation:
The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())"
Output:
4
Explanation:
The longest valid parentheses substring is "()()".
Example 3:
Input: s = ""
Output:
0
Constraints:
0 <= s.length <= 3 * 104
s[i]
is'('
, or')'
.
Runtime: 0 ms, faster than 100%
Memory Usage: 3.5 MB, less than 26.84%
func longestValidParentheses(s string) int {
stack := []int{-1}
res := 0
for i:=0; i<len(s); i++ {
if s[i] == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack) - 1]
if len(stack) == 0 {
stack = append(stack, i)
} else {
l := i - stack[len(stack) - 1]
res = max(res, l)
}
}
}
return res
}
func max(a, b int) int {
if a > b { return a }
return b
}