题目名称

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

示例

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

题解

利用栈来模拟括号的闭合及左右指针移动的方式
首先定义左右指针 left 和 right,并将初始值设置为 0，设置栈 stack 为空数组，利用 push 和 pop 方法模拟栈的输入和输出

当遇到左括号时，将左括号的序号记录到stack 中，并移动右指针

当遇到右括号时，首先需要判断栈内是否包含元素，如果不包含元素，此时先记录下有效括号子串的长度，并将左右指针的值记录为右括号序列 +1
如果栈内包含元素 则栈输出一个内容，此时计算一次有效括号子串的长度，右指针 +1

遍历完字符串后，如果栈内不包含元素，输出左右指针的差和最大子串长度的最大值
如果包含元素，则将 右指针与栈顶元素序号 求差，并输出最大子串长度的最大值

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {string} s
 * @return {number}
 */
 var longestValidParentheses = function(s) {
  let stack = [], left = 0, right = 0, max = 0, total = 0
  while(left <= right && right < s.length) {
    if(s[right] === ")") {
      if(stack.length === 0) {
        max = Math.max(right - left, max)
        stack = []
        right++
        left = right
      } else {
        right++
        stack.pop()
        max = Math.max(right - (stack.length ? stack[stack.length - 1] : left), max)
      }
    } else {
      right++
      stack.push(right)
    }
  }
  if(stack.length) {
    return Math.max(right - stack[stack.length - 1], max)
  }
  return Math.max(right - left, max)
};