leetcode 32. 最长有效括号 js实现
2023-09-14 09:07:43 时间
https://leetcode.cn/problems/longest-valid-parentheses/
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
示例 3:
输入:s = ""
输出:0
提示:
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
/** * @param {string} s * @return {number} */ // 算法思路: // 我们利用一个栈,里面先存入一个-1,方便后面计算有效子串长度,我们栈中的栈首元素是为后面计算有效长度做标记。 // 遍历字符串, // 若遇到'(',就把下标入栈; // 若遇到')',就出栈; // 若栈为空,说明该子串无效,因为我们的栈首存放的是标记位,并非'('的下标,那么我们就把当前的i入栈,作为新子串的标记位; // 若栈不为空,说明该字串有效,那么更新最长子串长度result = Math.max(result, i-stack.peek()); // 该算法的巧妙之处,正是栈首存放的是标记位,而非记录'('的下标。 var longestValidParentheses = function(s) { let max = 0 if (s.length < 1) return max let len = s.length // 栈顶之所有加入一个-1,纯粹是为了方便计算有效括号的长度 // 不然就需要手动调整为i-j+1;同时而确保第一个字符为")"时不需要特殊处理 let stack = [-1] for(let i = 0; i < len; i++) { let value = s[i] if (value === '(') { stack.push(i) } else if (value === ')') { stack.pop() // 栈顶加入一个pivot字符")",实际上是方便计算有效括号串长度 if (stack.length < 1) { stack.push(i) } else { max = Math.max(max, i - stack[stack.length - 1]) } } } return max };
参考链接
相关文章
- leetcode 258. 各位相加 js 实现
- leetcode 191 二进制中1的个数 js 实现
- ☆打卡算法☆LeetCode 208. 实现 Trie (前缀树) 算法解析
- leetcode 3. 无重复字符的最长子串 js 实现
- leetcode 141. 环形链表 js 实现
- JS设置定时器_js设置定时器
- leetcode 300. 最长递增子序列 js 动态规划实现
- 用Js怒刷LeetCode_2023-02-27
- leetcode_两数之和
- LeetCode题解——哈希表篇
- JavaScript刷LeetCode之双指针技巧(下)
- 【JS 逆向百例】猿人学系列 web 比赛第五题:js 混淆 - 乱码增强,详细剖析
- 【JS 逆向百例】猿人学系列 web 比赛第二题:js 混淆 - 动态 cookie,详细剖析
- clipboard.js:最轻便的复制页面内容到剪切板的JS
- Leetcode(153) Find Minimum in Rotated Sorted Array详解编程语言
- 使用 JS 操作 Redis:实现强大数据存储.(js调用redis)
- 使用JS在网页中连接Oracle数据库(js网页链接oracle)
- 使用JS操作Oracle数据库探索潜在可能性(js和oracle数据库)