0032.最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1： 输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"

示例 2： 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"

示例 3： 输入：s = "" 输出：0

提示： 0 <= s.length <= 3 * 10⁴ s[i] 为 '(' 或 ')'

解题思路：

  • 维护一个栈，遇到（ 入栈，遇到 ） 弹出栈顶元素
  • 栈为空，当前右括号为新的起始点(引入-1为辅助栈元素)
  • 更新最长括号长度
func longestValidParentheses(s string) int {
	  // 假设我们的字符串是 "()"，这时如果没有初始的-1在栈中，那么在遇到第一个右括号时，栈为空，无法确定有效括号的起始点。因此，我们将-1作为初始值放入栈中，当遇到右括号时，就可以直接使用它作为起始点。
	  stack := []int{-1} // 栈，初始化时压入-1作为辅助计算长度
	  maxLength := 0
      
	  for i, char := range s {
	  	if char == '(' { // 左括号
	  		stack = append(stack, i)
	  	} else { // 右括号
	  		stack = stack[:len(stack)-1] // 弹出栈顶元素
	  		if len(stack) == 0 {         // 栈为空，当前右括号为新的起始点
	  			stack = append(stack, i)
	  		} else { // 更新最长有效括号长度
	  			length := i - stack[len(stack)-1]
	  			if length > maxLength {
	  				maxLength = length
	  			}
	  		}
	  	}
	  }
      
	  return maxLength
}