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 ')'.

解題

​這隻影片中的第三種解法,使用 stack。
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
}