LeetCode.32 - 最长有效括号

• LeetCode - 32. 最长有效括号

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

思路

1. 任意一段合法子串里，任意前缀均满足左括号个数不小于右括号个数
2. 将字符串依次入栈
3. 待入栈元素为 ( 时，stack.push('(')
4. 待入栈元素为 ) 时
   1. 持续将不为 ( 的栈顶元素进行 pop，而后累加到 sum 中
   2. 若栈中无 ( 元素，不作额外操作
   3. 若栈中存在 ( 元素，stack.pop()，sum += 2，继续将不为 ( 的栈顶元素进行 pop 并累加到 sum 中，而后 stack.push(sum)
   4. sum 的最大值即所求结果

var longestValidParentheses = function (s) {
  const stack = []
  let result = 0
  for (const char of s) {
    if (char === '(') {
      stack.push('(')
      continue
    }
    // 下方逻辑处理 char === ')' 时
    let sum = 0
    while (stack.length > 0 && stack[stack.length - 1] !== '(') {
      sum += stack.pop()
    }
    if (stack.length > 0) {
      stack.pop()
      sum += 2
      while (stack.length > 0 && stack[stack.length - 1] !== '(') {
        sum += stack.pop()
      }
      stack.push(sum)
    }
    result = Math.max(result, sum)
  }
  return result
}