题目描述补充

题目：最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

有效括号必须满足以下条件：

• 左括号 ( 必须用相同数量的右括号 ) 包裹起来。
• 每个右括号 ) 必须有一个对应的左括号 (。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串是 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串是 "()()"

示例 3:

输入: ""
输出: 0

PHP 示例代码

function longestValidParentheses($s) {
    $maxLen = 0;
    $stack = [];
    $left = -1; // 记录左括号的位置

    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] == '(') {
            $stack[] = $i;
        } else {
            if (empty($stack)) {
                $left = $i; // 当栈为空时，更新left为当前位置
            } else {
                array_pop($stack);
                if (empty($stack)) {
                    // 栈为空，说明从left到i都是有效括号
                    $maxLen = max($maxLen, $i - $left);
                } else {
                    // 栈不为空，则计算当前位置到栈顶元素位置的距离
                    $maxLen = max($maxLen, $i - $stack[count($stack) - 1]);
                }
            }
        }
    }

    return $maxLen;
}

// 示例
echo longestValidParentheses("(()"); // 输出 2
echo longestValidParentheses(")()())"); // 输出 4
echo longestValidParentheses(""); // 输出 0

Python 示例代码

def longestValidParentheses(s):
    max_len = 0
    stack = []

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            if not stack:
                start = i + 1
            else:
                stack.pop()
                if not stack:
                    max_len = max(max_len, i - start + 1)
                else:
                    max_len = max(max_len, i - stack[-1])

    return max_len

# 示例
print(longestValidParentheses("(()"))  # 输出 2
print(longestValidParentheses(")()())"))  # 输出 4
print(longestValidParentheses(""))  # 输出 0

JavaScript 示例代码

function longestValidParentheses(s) {
    let maxLen = 0;
    const stack = [];
    let left = -1;

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            if (stack.length === 0) {
                left = i;
            } else {
                stack.pop();
                if (stack.length === 0) {
                    maxLen = Math.max(maxLen, i - left);
                } else {
                    maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
                }
            }
        }
    }

    return maxLen;
}

// 示例
console.log(longestValidParentheses("(()")); // 输出 2
console.log(longestValidParentheses(")()())")); // 输出 4
console.log(longestValidParentheses("")); // 输出 0

// 码小课网站中有更多相关内容分享给大家学习

以上代码示例展示了如何使用栈来解决“最长有效括号”问题，并给出了 PHP、Python 和 JavaScript 的实现方式。