题目描述

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

题目来源

https://leetcode-cn.com/problems/longest-valid-parentheses/

题目实例

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

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

解题代码

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    var op_stack = [];
    var tmp_result = 0;
    var len = s.length;
    s = s + '#';
    var dp = [];
    for(let j = 0;j <= len;j++){
        if(s[j] == '('){
            op_stack.push(s[j]);
            dp.push(tmp_result);
        }else if(s[j] == ')'){
            let op = op_stack.pop();
            if(op == '('){
                tmp_result+=2;
                dp.pop();
            }else{
                dp.push(tmp_result);
            }
        }else if(s[j] == '#'){
            dp.push(tmp_result);
        }
    }
    var result = tmp = dp[0];
    for(let n = 1;n < dp.length;n++){
        tmp = dp[n]-dp[n-1];
        if(tmp > result){
            result = tmp;
        }
    }
    return result;
};