leetcode 32. 最长有效括号 (困难) | 您所在的位置:网站首页 › 最长有效括号子串长度递归版 › leetcode 32. 最长有效括号 (困难) |
作者简介:C/C++ 、Golang 领域耕耘者,创作者 个人主页:作者主页 活动地址:CSDN21天学习挑战赛 题目来源: leetcode官网 如果感觉博主的文章还不错的话,还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~ 文章目录 💜 题目描述🧡 算法分析💚 代码实现💙 时间复杂度分析 💜 题目描述给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例1: 输入:s = “(()” 输出:2 解释:最长有效括号子串是 “()” 示例2: 输入:s = “)()())” 输出:4 解释:最长有效括号子串是 “()()” 示例 3: 输入:s = “” 输出:0 🧡 算法分析此题方法之一是用栈 我们通过标记合法的括号,可以得出,每一段合法的括号在字符串出现的位置一定是连续且不相交的 做括号匹配的这题可以用栈存储相应的信息,算法过程为: 用栈维护当前待匹配的左括号的位置,同时用 start 记录一个新的可能合法的子串的起始位置,初始设为0如果s[i] ==‘(’,那么把i进栈如果s[i] == ‘)’,那么弹出栈顶元素 (代表栈顶的左括号匹配到了右括号),出栈后:如果栈为空,说明以当前右括号为右端点的合法括号序列的左端点为start,则更新答案 i - start + 1 如果栈不为空,说明以当前右括号为右端点的合法括号序列的左端点为栈顶元素的下一个元素,则更新答案i - st.top()
5、最后返回答案即可 💚 代码实现 class Solution { public: int longestValidParentheses(string s) { stack st; int re = 0; for(int i = 0, start = 0; i if(st.size()) { st.pop(); if(st.empty()) re = max(re, i - start + 1); else re= max(re, i - st.top()); // 因为之前已经弹出来了一个元素 (st.top() + 1) - 1 } else start = i + 1; // 更新 } } return re; } };执行结果: 其中字符串只遍历一次, 时间复杂度为O(n) 如果觉得对你有帮助的话: 👍 点赞,你的认可是我创作的动力! 🧡 收藏,你的青睐是我努力的方向! ✏️ 评论,你的意见是我进步的财富! |
CopyRight 2018-2019 实验室设备网 版权所有 |