var longestValidParentheses = function (s) {
let stack = [],
start = -1,
max = 0;
for (let i = 0, len = s.length; i < len; ++i) {
if (s[i] === "(") {
stack.push(i);
} else {
if (stack.length === 0) {
start = i;
} else {
stack.pop();
if (stack.length === 0) {
max = Math.max(max, i - start);
} else {
max = Math.max(max, i - stack[stack.length - 1]);
}
}
}
}
return max;
};
如果当前字符串是”(“,则将当前字符串的下标入栈,如果当前字符串是”)”,则分两种情况:
- 当前栈为空,说明前一段匹配已经结束,现在的字符串为”)”,所以重新开始计算匹配的括号对长度
- 当前栈不为空,则把栈顶的元素出栈,出栈后又有两种情况:
- 栈为空,说明这一阶段已经匹配完成,重新计算下max的值,
max = Math.max(max, i - start)
,因为start只有在栈为空,并且下一字符串为”)”才会重置,所以i-start
可能会包含多段匹配的长度,例如"()()"
- 栈不为空,这一阶段还没有匹配完成,但是也要重新计算max的值,因为有可能到最后这一阶段的匹配都不会完成
max = Math.max(max, i - stack[stack.length - 1])
- 栈为空,说明这一阶段已经匹配完成,重新计算下max的值,