最长有效括号

题目

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

提示:

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

示例

输入: s = )()())

输出: 4

解释: 最长有效括号子串是 ()()

题解

我们始终保持栈底元素为当前已经遍历过的元素中最后一个没有被匹配的右括号的下标:

• 对于遇到的每个 '(', 我们将它的下标放入栈中
• 对于遇到的每个 ')', 我们先弹出栈顶元素表示匹配了当前右括号:
  • 如果栈为空, 说明当前的右括号为没有被匹配的右括号, 我们将其下标放入栈中来更新最后一个没有被匹配的右括号的下标
  • 如果栈不为空, 当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度

由于我们要保证栈底元素为右括号的下标, 如果 s 的第一个元素是 '(', 根据要求就会 push 到栈中, 这就无法满足栈底元素为右括号的下标, 因此初始化栈时要放入一个值为 -1 的元素.

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  const n = s.length
  const stack = [-1]

  let max = 0
  for (let i = 0; i < n; i++) {
    if (s[i] === '(') {
      stack.push(i)
    } else {
      stack.pop()

      if (stack.length !== 0) {
        max = Math.max(i - stack[stack.length - 1], max)
      } else {
        stack.push(i)
      }
    }
  }

  return max
}

Rust

use std::cmp;

pub fn longest_valid_parentheses(s: String) -> i32 {
    let mut max = 0;
    let mut stack = vec![-1];

    for (i, ch) in s.chars().enumerate() {
        if ch == '(' {
            stack.push(i as i32);
        } else {
            stack.pop();

            if stack.len() != 0 {
                max = cmp::max(max, i as i32 - stack.last().unwrap());
            } else {
                stack.push(i as i32);
            }
        }
    }

    max
}

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)