leetcode 32. Longest Valid Parentheses
2014 年 10 月 12 日
难题
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; };