leetcode 32. 最长有效括号 js实现

/**
 * @param {string} s
 * @return {number}
 */

// 算法思路：
// 我们利用一个栈，里面先存入一个-1，方便后面计算有效子串长度，我们栈中的栈首元素是为后面计算有效长度做标记。
// 遍历字符串，
// 若遇到'('，就把下标入栈；
// 若遇到')'，就出栈；
// 若栈为空，说明该子串无效，因为我们的栈首存放的是标记位，并非'('的下标，那么我们就把当前的i入栈，作为新子串的标记位；
// 若栈不为空，说明该字串有效，那么更新最长子串长度result = Math.max(result, i-stack.peek());
// 该算法的巧妙之处，正是栈首存放的是标记位，而非记录'('的下标。
var longestValidParentheses = function(s) {
    let max = 0
    if (s.length < 1) return max

    let len = s.length

    // 栈顶之所有加入一个-1,纯粹是为了方便计算有效括号的长度
    // 不然就需要手动调整为i-j+1;同时而确保第一个字符为")"时不需要特殊处理
    let stack = [-1]

    for(let i = 0; i < len; i++) {
        let value = s[i]
        if (value === '(') {
        stack.push(i)
        } else if (value === ')') {
        stack.pop()


        // 栈顶加入一个pivot字符")",实际上是方便计算有效括号串长度
        if (stack.length < 1) {
            stack.push(i)
        } else {
            max = Math.max(max, i - stack[stack.length - 1])
        }
        }
    }


    return max
};