介绍

给出一个由开括号和闭括号组成的字符串，找出最长的有效括号子串的长度。

一个简单的方法是找到给定字符串的所有子串。对于每个字符串，检查它是否是一个有效的字符串。如果是有效的并且长度超过了目前的最大长度，那么就更新最大长度。我们可以使用堆栈在线性时间内检查一个子串是否有效（详见 Check for Balanced Brackets in an expression (well-formedness) using Stack (opens new window)）。这个方案的时间复杂度是 O (n^2).

一个高效的解决方案可以在 O (n) 时间内解决这个问题，其思路是将以前的起始括号的索引存储在一个堆栈中。栈的第一个元素是一个特殊的元素，它提供了有效子串开始前的索引（下一个有效字符串的基数）。

实现

JavaScript

/*
  LeetCode -> https://leetcode.com/problems/longest-valid-parentheses/

  Given a string containing just the characters '(' and ')',
  find the length of the longest valid (well-formed) parentheses substring.
*/

export const longestValidParentheses = (s) => {
  const n = s.length
  const stack = []

  // storing results
  const res = new Array(n).fill(-Infinity)

  for (let i = 0; i < n; i++) {
    const bracket = s[i]

    if (bracket === ')' && s[stack[stack.length - 1]] === '(') {
      res[i] = 1
      res[stack[stack.length - 1]] = 1
      stack.pop()
    } else stack.push(i)
  }

  // summing all adjacent valid
  for (let i = 1; i < n; i++) res[i] = Math.max(res[i], res[i] + res[i - 1])

  // adding 0 if there are none so it will return 0 instead of -Infinity
  res.push(0)
  return Math.max(...res)
}

或者：

// JavaScript Program for the above approach
function findMaxLen(str) {
 let n = str.length;
 // Create a stack and push -1 as initial index to it.
 let stk = [];
 stk.push(-1);
 // Initialize result
 let result = 0;

 // Traverse all characters of given string
 for (let i = 0; i < n; i++) {
   // If opening bracket, push index of it
   if (str.charAt(i) == '(') stk.push(i);
   // If closing bracket, i.e.,str[i] = ')'
   else if (stk.length != 0) {
     // Pop the previous opening bracket's index
     stk.pop();
     // Check if this length formed with base of current valid substring is more than max so far
     // 检查该长度与当前有效子串的基数形成的长度是否超过迄今为止的最大值
     result = Math.max(result, i - stk[stk.length - 1]);
     // If stack is empty. push current index as base for next valid substring (if any)
   } else stk.push(i);
 }

 return result;
}

参考

• Length of the longest valid substring - GeeksforGeeks (opens new window)