[leetcode] [32] [javascript] Longest Valid Parentheses

這幾天困了我很久的ㄧ題

/**

 * @param {string} s

 * @return {number}

 */

var longestValidParentheses = function(s) {

    

    var i = 0;

    var max = 0;

    var stack = [];

    var stack_ind = [];

    

    while(i<=s.length-1){

        var pop = 0;

        if(s[i] == ')'){

            if(stack.length > 0){

                pop = stack.pop();

                stack_ind[pop] = true;

                stack_ind[i] = true;

            }else{

                stack_ind[i] = false;

            }

            i++;

            continue;

        }else{

            stack.push(i);

            stack_ind[i] = false;

            i++;

            continue;

        }

    }

    i = 0;

    var count = 0;

    while(i<=s.length-1){

        if(stack_ind[i]){

            count++;

            if(count > max){

                max = count;

            }

        }else{

            count = 0;

        }

        i++;

    }

    

    return max;

    

}; 

原本一直TLE的寫法

 

/**

 * @param {string} s

 * @return {number}

 */

var longestValidParentheses = function(s) {

  

    var i = 0;

    var max = 0;

    while(i<s.length-1){

        // console.log('i:', i);

        if(s[i] == ')'){

            i++;

            continue;

        }

      

        var stack = [];

        var stack_ind = [];

        var count = 0;

        var j = i;

        while(j<=s.length-1){

            if(s[j] == '('){

                if(j != s.length-1){

                    stack.push(s[j]);

                    stack_ind.push(j);

                }

                j++;

            }else{

                if(stack.length > 0){

                    stack.pop();

                    stack_ind.pop();

                    j++;

                    count++;

                    if(stack.length === 0){

                        if(count*2 > max){

                            max = count * 2;

                            console.log('max:', max);

                        }

                    }

                }else{

                    j++;

                    break;

                }

            }

        }

      

        if(stack.length === 0){

            i = i + (j-i);

        }else{

            i = stack_ind[0] + 1;

        }

    }

    return max;

  

};