本文共 1859 字,大约阅读时间需要 6 分钟。
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"输出: 2解释: 最长有效括号子串为 "()"示例 2:
输入: ")()())"输出: 4解释: 最长有效括号子串为 "()()"/** * @param {string} s * @return {number} */var longestValidParentheses = function(s) { //用栈来判断括号是否有效 //数字代表括号 -1代表左括号,0代表右括号,1代表已经匹配的括号 //当前待压栈元素有两种 '(' 和 ')' //如果为'('把-1入栈 //如果为')',当前栈顶有四种可能: // 空:将取出的值入栈,再将0入栈 // -1,把-1取出,1+之前取出的值入栈 // 0, 把0+之前取出的值入栈,再将0入栈 // >0, 把栈顶取出,并记录下来,然后继续取下一个栈顶 // 最后找出栈中大于0连续加起来的最大值再乘2就是最后结果 let stackLen = 0;//栈的长度 let stack = [];//栈 for(let i = 0, len = s.length; i < len; i++) { if(s[i]=='(') { stack.push(-1); stackLen++; } else{ let allVal=0; while(stackLen>=0) { if(stackLen==0) { stack.push(allVal); stack.push(0) stackLen+=2; break; }else { if(stack[stackLen-1]==-1) { stack.pop(); stack.push(1+allVal); break; }else if(stack[stackLen-1]==0) { stack.push(allVal); stack.push(0); stackLen+=2; break; }else { allVal+=stack.pop(); stackLen--; } } } } // console.log(stack) } console.log(stack) let res=0, max=-9999; for(let i = 0; i < stackLen; i++) { if(stack[i]>0) { res+=stack[i]; }else{ res=0; } if(res>max) { max = res; } } return max*2>0?max*2:0;};
转载于:https://blog.51cto.com/14127734/2395245