博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最长有效括号
阅读量:7145 次
发布时间:2019-06-29

本文共 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

你可能感兴趣的文章
C#使用Xamarin开发可移植移动应用(3.Xamarin.Views控件)附源码
查看>>
Java 模拟基于UDP的Socket通信
查看>>
有关 Windows Lite 的一切,只为对抗 Chrome OS?
查看>>
NG-ZORRO 7.0.1 发布,Ant Design 的 Angular 实现
查看>>
scala笔记(三)
查看>>
大数据应用安全研究报告(11家公司实践详解)
查看>>
MES之殇和工业IOT之春
查看>>
阿里云网络漏洞扫描系统AVDS(商业化)发布
查看>>
python splinter 小坑说明
查看>>
控制input输入格式
查看>>
一次XEN启动中的错误捕获
查看>>
esxi嵌套华为Fusioncomputer安装VRM几个关键步骤。
查看>>
DNS设置引起的登录延迟
查看>>
saltstack之SLS文件
查看>>
JAVA构建缓存
查看>>
解决:Loading kernel module CAP_SYS_MODULE CAP_NET_ADMIN alias netdev-eth0 instead
查看>>
wav2letter-基于深度学习的语音识别
查看>>
Java class.forname()和newinstance
查看>>
学习计划书
查看>>
[iOS Animation]-CALayer 视觉效果
查看>>