题目描述给你一个只包含(和)的字符串找出其中最长有效格式正确且连续括号子串的长度。左右括号匹配即每个左括号都有对应的右括号将其闭合的字符串是格式正确的例如(()())。示例输入s (()→ 输出2最长有效括号子串是())输入s )()())→ 输出4最长有效括号子串是()())输入s → 输出0解题思路总览方法思路时间复杂度空间复杂度动态规划dp[i]表示以第i个字符结尾的最长有效括号长度O(n)O(n)栈栈中存索引遇到)时弹出并计算长度O(n)O(n)双指针两遍扫描分别从左到右和从右到左处理不匹配的情况O(n)O(1)本题采用动态规划方法。完整代码classSolution{public:intlongestValidParentheses(string s){intmaxLen0,ns.size();vectorintdp(n,0);for(inti1;in;i){if(s[i])){if(s[i-1](){dp[i](i2?dp[i-2]:0)2;}elseif(i-dp[i-1]0s[i-dp[i-1]-1](){dp[i]dp[i-1]((i-dp[i-1])2?dp[i-dp[i-1]-2]:0)2;}maxLenmax(maxLen,dp[i]);}}returnmaxLen;}};算法流程图输入: s )()()) 初始化: n 6 dp[0...5] 0 maxLen 0 i 1, s[1] (: s[1] )? 否跳过 maxLen 0 i 2, s[2] ): s[2] )? 是 s[1] (? 是 dp[2] dp[0] 2 0 2 2 maxLen max(0, 2) 2 i 3, s[3] (: s[3] )? 否跳过 maxLen 2 i 4, s[4] ): s[4] )? 是 s[3] (? 是 dp[4] dp[2] 2 2 2 4 maxLen max(2, 4) 4 i 5, s[5] ): s[5] )? 是 s[4] (? 否进入 else if i - dp[4] 5 - 4 1 0 s[1] (? 是 dp[5] dp[4] dp[0] 2 4 0 2 6 maxLen max(4, 6) 6 最终 maxLen 6 输出: 6逐行解析intmaxLen0,ns.size();含义maxLen记录全局最长有效括号长度n记录字符串长度。vectorintdp(n,0);含义dp[i]表示以第i个字符结尾的最长有效括号子串长度。初始化为 0。for(inti1;in;i)含义从索引 1 开始遍历因为 dp[0] 只能是 0不需要计算。if(s[i]))含义只有当当前字符是)时才可能形成有效括号。if(s[i-1]()含义情况一...形式的最近匹配。例如()或(...)()dp[i](i2?dp[i-2]:0)2;含义如果是()形式长度为 2 加上 dp[i-2]之前已匹配的长度。需要判断 i-2 是否 0。elseif(i-dp[i-1]0s[i-dp[i-1]-1]()含义情况二类似(...])的形式其中...已经是有效括号段。例如(())中 s[3]‘)’ 时i-dp[i-1]3-21s[0]‘(’形成匹配。dp[i]dp[i-1]((i-dp[i-1])2?dp[i-dp[i-1]-2]:0)2;含义dp[i - 1]之前已经匹配的有效括号长度((i - dp[i - 1]) 2 ? dp[i - dp[i - 1] - 2] : 0)加上再之前的有效括号长度 2加上当前匹配的()maxLenmax(maxLen,dp[i]);含义更新全局最长长度。状态转移图解情况一() 形式 i-1 i ( ) dp[i] dp[i-2] 2 情况二(...]) 形式 i-1 i ... ( ... ) ) ^dp[i-1] ^ i - dp[i-1] - 1 (与 i 配对的 ( 的位置) dp[i] dp[i-1] dp[i - dp[i-1] - 2] 2复杂度分析复杂度值说明时间复杂度O(n)只需遍历一次字符串空间复杂度O(n)dp 数组大小为 n面试追问 FAQ问题答案为什么从i 1开始而不是i 0因为 dp[0] 一定是 0空字符串无法形成有效括号从 1 开始可以减少边界判断dp[i]为什么要定义为「以第 i 个字符结尾」这样可以利用 dp[i-1] 的值实现 O(1) 转移。如果是「前 i 个字符中最长」就无法利用之前的结果栈方法是怎么工作的栈中存左括号的索引遇到右括号时弹出。如果弹出后栈非空当前长度 i - 栈顶索引如果栈空当前长度 i 1双指针方法的原理从左到右扫描时遇到不匹配的)就重置从右到左扫描时遇到不匹配的(就重置。两遍扫描可以覆盖所有情况如何输出具体的最长有效括号子串在计算 dp[i] 时记录 maxLen 对应的位置然后从该位置向前截取 maxLen 长度的子串进阶如何 O(1) 空间使用双指针方法分别从左到右和从右到左扫描处理不匹配的括号情况相关题目题号题目难度核心思路32最长有效括号困难动态规划/栈/双指针20有效的括号简单栈22括号生成中等DFS/回溯301删除无效的括号困难BFS/DFS总结要点内容核心思想动态规划以每个)结尾计算最长有效括号长度状态定义dp[i] 以第 i 个字符结尾的最长有效括号长度状态转移情况一(), dp[i] dp[i-2] 2状态转移情况二(...]), dp[i] dp[i-1] dp[i-dp[i-1]-2] 2边界处理需要判断索引是否越界结果返回 maxLen
【力扣100题】50.最长有效括号
题目描述给你一个只包含(和)的字符串找出其中最长有效格式正确且连续括号子串的长度。左右括号匹配即每个左括号都有对应的右括号将其闭合的字符串是格式正确的例如(()())。示例输入s (()→ 输出2最长有效括号子串是())输入s )()())→ 输出4最长有效括号子串是()())输入s → 输出0解题思路总览方法思路时间复杂度空间复杂度动态规划dp[i]表示以第i个字符结尾的最长有效括号长度O(n)O(n)栈栈中存索引遇到)时弹出并计算长度O(n)O(n)双指针两遍扫描分别从左到右和从右到左处理不匹配的情况O(n)O(1)本题采用动态规划方法。完整代码classSolution{public:intlongestValidParentheses(string s){intmaxLen0,ns.size();vectorintdp(n,0);for(inti1;in;i){if(s[i])){if(s[i-1](){dp[i](i2?dp[i-2]:0)2;}elseif(i-dp[i-1]0s[i-dp[i-1]-1](){dp[i]dp[i-1]((i-dp[i-1])2?dp[i-dp[i-1]-2]:0)2;}maxLenmax(maxLen,dp[i]);}}returnmaxLen;}};算法流程图输入: s )()()) 初始化: n 6 dp[0...5] 0 maxLen 0 i 1, s[1] (: s[1] )? 否跳过 maxLen 0 i 2, s[2] ): s[2] )? 是 s[1] (? 是 dp[2] dp[0] 2 0 2 2 maxLen max(0, 2) 2 i 3, s[3] (: s[3] )? 否跳过 maxLen 2 i 4, s[4] ): s[4] )? 是 s[3] (? 是 dp[4] dp[2] 2 2 2 4 maxLen max(2, 4) 4 i 5, s[5] ): s[5] )? 是 s[4] (? 否进入 else if i - dp[4] 5 - 4 1 0 s[1] (? 是 dp[5] dp[4] dp[0] 2 4 0 2 6 maxLen max(4, 6) 6 最终 maxLen 6 输出: 6逐行解析intmaxLen0,ns.size();含义maxLen记录全局最长有效括号长度n记录字符串长度。vectorintdp(n,0);含义dp[i]表示以第i个字符结尾的最长有效括号子串长度。初始化为 0。for(inti1;in;i)含义从索引 1 开始遍历因为 dp[0] 只能是 0不需要计算。if(s[i]))含义只有当当前字符是)时才可能形成有效括号。if(s[i-1]()含义情况一...形式的最近匹配。例如()或(...)()dp[i](i2?dp[i-2]:0)2;含义如果是()形式长度为 2 加上 dp[i-2]之前已匹配的长度。需要判断 i-2 是否 0。elseif(i-dp[i-1]0s[i-dp[i-1]-1]()含义情况二类似(...])的形式其中...已经是有效括号段。例如(())中 s[3]‘)’ 时i-dp[i-1]3-21s[0]‘(’形成匹配。dp[i]dp[i-1]((i-dp[i-1])2?dp[i-dp[i-1]-2]:0)2;含义dp[i - 1]之前已经匹配的有效括号长度((i - dp[i - 1]) 2 ? dp[i - dp[i - 1] - 2] : 0)加上再之前的有效括号长度 2加上当前匹配的()maxLenmax(maxLen,dp[i]);含义更新全局最长长度。状态转移图解情况一() 形式 i-1 i ( ) dp[i] dp[i-2] 2 情况二(...]) 形式 i-1 i ... ( ... ) ) ^dp[i-1] ^ i - dp[i-1] - 1 (与 i 配对的 ( 的位置) dp[i] dp[i-1] dp[i - dp[i-1] - 2] 2复杂度分析复杂度值说明时间复杂度O(n)只需遍历一次字符串空间复杂度O(n)dp 数组大小为 n面试追问 FAQ问题答案为什么从i 1开始而不是i 0因为 dp[0] 一定是 0空字符串无法形成有效括号从 1 开始可以减少边界判断dp[i]为什么要定义为「以第 i 个字符结尾」这样可以利用 dp[i-1] 的值实现 O(1) 转移。如果是「前 i 个字符中最长」就无法利用之前的结果栈方法是怎么工作的栈中存左括号的索引遇到右括号时弹出。如果弹出后栈非空当前长度 i - 栈顶索引如果栈空当前长度 i 1双指针方法的原理从左到右扫描时遇到不匹配的)就重置从右到左扫描时遇到不匹配的(就重置。两遍扫描可以覆盖所有情况如何输出具体的最长有效括号子串在计算 dp[i] 时记录 maxLen 对应的位置然后从该位置向前截取 maxLen 长度的子串进阶如何 O(1) 空间使用双指针方法分别从左到右和从右到左扫描处理不匹配的括号情况相关题目题号题目难度核心思路32最长有效括号困难动态规划/栈/双指针20有效的括号简单栈22括号生成中等DFS/回溯301删除无效的括号困难BFS/DFS总结要点内容核心思想动态规划以每个)结尾计算最长有效括号长度状态定义dp[i] 以第 i 个字符结尾的最长有效括号长度状态转移情况一(), dp[i] dp[i-2] 2状态转移情况二(...]), dp[i] dp[i-1] dp[i-dp[i-1]-2] 2边界处理需要判断索引是否越界结果返回 maxLen
