【算法题-困难】最长有效括号

困难算法题，最长有效括号，使用 JavaScript 语言编写

题目

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

输入格式

包含 ( 和 ) 的字符串

输出格式

有效括号子串的长度

输入样例

输入样例一：

(()

输入样例二：

)()(()))

输入样例三：

输出样例

输出样例一：

2

输出样例二：

6

输出样例三：

0

分析

1. 初始化一个栈，用于存储括号的索引。
2. 初始化一个变量 max_length，用于记录最长有效括号子串的长度。
3. 将栈初始化为 [-1]，以便处理边界情况。
4. 遍历字符串的每个字符及其索引：

• 如果字符是 (，将其索引压入栈中。
• 如果字符是 )，弹出栈顶元素。
  • 如果栈为空，将当前索引压入栈中。
  • 如果栈不为空，计算当前有效括号子串的长度，并更新 max_length。

1. 返回 max_length。

解答

// 这是题目要求的输入格式
let inputs = `
()(()
`;

inputs = inputs.trim();

function longestValidParentheses(s) {
  // 初始值 -1 确保了在计算第一个有效括号子串长度时，能够正确计算长度。例如，对于字符串 ()()，在遇到第一个 ) 时，栈中只有 -1，计算长度为 1 - (-1) = 2。
  const stack = [-1];
  let maxLength = 0;

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i); // 左括号的索引入栈
    } else {
      stack.pop(); // 右括号，弹出栈顶元素
      if (stack.length === 0) {
        // 如果栈为空，说明当前右括号没有匹配的左括号，将当前索引 i 压入栈中，作为新的基准。
        stack.push(i);
      } else {
        // 如果栈不为空，计算当前有效括号子串的长度，即 i - stack[stack.length - 1]，并更新 maxLength。
        // maxLength = i - stack[stack.length - 1]; // 错误写法，不能通过用例 "()(()"。
        maxLength = Math.max(maxLength, i - stack[stack.length - 1]);
      }
    }
  }

  return maxLength;
}

// 示例
console.log(longestValidParentheses(inputs));

解释