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
}