LeetCode-热题100：32. 最长有效括号

题目描述

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

示例 1：

输入： s = “(()”
输出： 2
解释： 最长有效括号子串是 “()”

示例 2：

输入： s = “)()())”
输出： 4
解释： 最长有效括号子串是 “()()”

示例 3：

输入： s = “”
输出： 0

提示：

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

代码及注释

func longestValidParentheses(s string) int {
    res := 0 // 用于存储最长有效括号子串的长度
    stack := []int{-1} // 使用栈来存储'('的下标

    // 遍历字符串 s
    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 {
                // 计算当前有效括号子串的长度，并更新 res
                res = max(res, i - stack[len(stack) - 1])
            }
        }
    }
    return res // 返回最长有效括号子串的长度
}

代码解释

1. 初始化：

   res := 0 // 用于存储最长有效括号子串的长度
   stack := []int{-1} // 使用栈来存储'('的下标
   

   • res 用于记录最长有效括号子串的长度。
   • stack 用于存储’('的下标，初始化时放入 -1 作为哨兵。

2. 遍历字符串 s：

   for i := 0; i < len(s); i++ {
   

   • 对字符串 s 进行遍历。

3. 处理 ‘(’：

   if s[i] == '(' {
       stack = append(stack, i)
   }
   

   • 如果遇到 ‘(’，将其下标 i 入栈。

4. 处理 ‘)’：

   } else {
       stack = stack[:len(stack) - 1]
       if len(stack) == 0 {
           stack = append(stack, i)
       } else {
           res = max(res, i - stack[len(stack) - 1])
       }
   }
   

   • 如果遇到 ‘)’，将栈顶元素出栈。
   • 如果栈为空，说明当前的 ‘)’ 无法匹配，将当前的下标 i 入栈。
   • 如果栈不为空，计算当前有效括号子串的长度 i - stack[len(stack) - 1]，并更新 res。

5. 返回结果：

   return res
   

   • 返回最长有效括号子串的长度 res。

使用栈来存储未匹配的括号的下标，时间复杂度为 O(n)，其中 n 是字符串 s 的长度。