原题链接：https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad

描述

给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。

例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .

思路

可以想到，从左向右扫描时，当")"数量比"("多时，括号字串已不合法，故此时将计数器清空，当两种括号数量相同时，更新最大值，但这样会漏掉一种情况：左括号的数量始终大于右括号的数量，如(()，这种情况求不出最长有效括号，所以还需要从右往左再扫描一次，当然判定条件要反过来。

代码

/**
 *
 * @param s string字符串
 * @return int整型
 */
function longestValidParentheses(s) {
  let left = 0;
  let right = 0;
  let max = 0;

  for (let i = 0; i < s.length; i++) {
    if (s[i] == "(") left++;
    if (s[i] == ")") right++;

    if (right > left) {
      right = left = 0;
      continue;
    }
    if (left === right) {
      max = Math.max(max, left);
    }
  }
  left = right = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] == "(") left++;
    if (s[i] == ")") right++;

    if (right < left) {
      right = left = 0;
      continue;
    }
    if (left === right) {
      max = Math.max(max, right);
    }
  }
  return max * 2;
}

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/148.html
最后修改时间：2022-04-23 21:24:36
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！