最长有效括号

[louzhedong]

习题

出处：LeetCode 算法第32题

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

示例 1:

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

示例 2:

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

思路

使用一个栈来保存最长匹配的字符串，每次遇到匹配的对，如果是和前面连续的，则使最大值加2。并使堆栈弹出两个值。

解答

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  var result = 0;
  var arrayStack = [0];
  s.split('').forEach(item => {
    if (item == '(') {
      arrayStack.push(0);
    } else {
      var length = arrayStack.length;
      if (length >= 2) {
        arrayStack[length - 2] += arrayStack.pop() + 2;
        result = Math.max(result, arrayStack[length - 2]);
      } else {
        arrayStack = [0];
      }
    }
  });
  return result;
};

console.log(longestValidParentheses(')(()())'));