零题目：算法(leetode,附思维导图+全解)300题(32)最长有效括号1题目描述2.解题概览(思维导图))3.AllSolutions1Scheme11)Code://Scheme1《滑动窗口法》。//通过：229/231，超时！//示例：太长无法列出。//思路：//1)初始化状态。//2)Core:窗口大小固定为tempL(range:[l,0])，不断穷尽所有可能的情况，然后处理//tempL:当前窗口大小，左右为左右当前窗口的两侧分别。//3)返回结果varlongestValidParentheses=function(s){//判断当前子串tempS是否为有效括号constisValidParentheses=(tempS='')=>{constl=tempS.length;让堆栈=[];for(leti=0;i0;tempL--){//优化：长度是奇数，当然不是！如果(tempL%2===1){继续;}for(letleft=0;left<(l-tempL+1);left++){constright=(left+tempL-1);//优化：最好最左边和最右边的字符必须分别是'(',')'！if(s[left]!=='('||s[right]!==')'){继续;}else{consttempS=s.slice(左,右+1);if(isValidParentheses(tempS)){//3)返回结果returntempL;}}}}//3.2)返回结果return0;};2解决方案21)代码：//解决方案2“动态编程”。//思路：//1）我们用dp[i]表示以i结尾的最长有效括号//2.1）如果s[i]是（，那么dp[i]一定等于0，因为不可能形成一个有效的括号Brackets//2.2)ifs[i]is),//2.2.1)andwhens[i-1]is(,thendp[i]=dp[i-2]+2;//2.2.2)并且当s[i-1]是)&&s[i-dp[i-1]-1]是(,那么dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]。//3)返回结果resLength//参考：//1)https://leetcode-cn.com/problems/longest-valid-parentheses/solution/dong-tai-gui-hua-si-lu-xiang-jie-c-by-zhanganan042/varlongestValidParentheses=function(s){//1)状态初始化constl=s.length;让dp=Array(l).fill(0),resLength=0;//2)core://1)我们用dp[i]表示以i结尾的最长有效括号//2.1)如果s[i]是(，那么dp[i]一定等于0，因为它不可能形成一个有效的括号//2.2)如果s[i]是),//2.2.1)并且当s[i-1]是(,那么dp[i]=dp[i-2]+2;//2.2.2)当s[i-1]是)&&s[i-dp[i-1]-1]是(,那么dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]。for(leti=0;i0&&s[i]===')'){if(s[i-1]==='('){dp[i]=((i-2>=0)?dp[i-2]+2:2);}elseif(s[i-1]===')'&&(i-dp[i-1]-1>=0)&&(s[i-dp[i-1]-1]==='(')){dp[i]=dp[i-1]+2+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0);}}resLength=Math.max(resLength,dp[i]);}//3）返回结果resLength返回resLength；}
