leetcode 32. Longest Valid Parentheses

难题

var longestValidParentheses = function(s) {
    if (s == null || s.length < 1) return 0;

        var maxans = 0;
        var stack = []
        stack.push(-1);
        for (var i = 0; i < s.length; i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (!stack.length) stack.push(i);
                else maxans = Math.max(maxans, i - stack[stack.length-1]);
            }
        }
        return maxans;

};

此题还有一种不用额外空间的解法,使用了两个变量 left 和 right,分别用来记录到当前位置时左括号和右括号的出现次数,当遇到左括号时,left 自增1,右括号时 right 自增1。对于最长有效的括号的子串,一定是左括号等于右括号的情况,此时就可以更新结果 res 了,一旦右括号数量超过左括号数量了,说明当前位置不能组成合法括号子串,left 和 right 重置为0。但是对于这种情况 "(()" 时,在遍历结束时左右子括号数都不相等,此时没法更新结果 res,但其实正确答案是2,怎么处理这种情况呢?答案是再反向遍历一遍,采取类似的机制,稍有不同的是此时若 left 大于 right 了,则重置0,这样就可以 cover 所有的情况了,参见代码如下:

var longestValidParentheses = function(s) {
    if (s == null || s.length < 1) return 0;

       var res = 0, left = 0, right = 0, n = s.length;
        for (var i = 0; i < n; ++i) {
            (s[i] == '(') ? ++left : ++right;
            if (left == right) res = Math.max(res, 2 * right);
            else if (right > left) left = right = 0;
        }
        left = right = 0;
        for (var i = n - 1; i >= 0; --i) {
            (s[i] == '(') ? ++left : ++right;
            if (left == right) res = Math.max(res, 2 * left);
            else if (left > right) left = right = 0;
        }
        return res;
};
上一篇:@Valid和@Validated的总结区分(转)


下一篇:20. Valid Parentheses做题报告