1. 题目解析与核心思路Longest Valid Parentheses最长有效括号是LeetCode上的一道经典动态规划/栈应用题目编号32难度等级为Hard。题目要求在一个仅包含(和)的字符串中找出最长的有效括号子串的长度。有效括号子串需要满足所有括号都能正确匹配闭合。1.1 问题定义与示例分析有效括号子串的判定标准每个左括号(必须有对应的右括号)匹配匹配的括号对必须正确嵌套不能交叉示例分析 输入)()()) 输出4 解释最长有效子串是()()1.2 暴力解法与复杂度分析最直观的解法是检查所有可能的子串是否有效生成所有可能的子串O(n^2)个子串对每个子串检查有效性O(n)时间记录最大有效长度时间复杂度O(n^3) —— 对于n3×10^4的字符串完全不可行2. 动态规划解法详解2.1 DP状态定义定义dp[i]表示以s[i]结尾的最长有效括号子串长度。关键观察点只有)能形成有效子串的结尾对于s[i])需要考察前一个字符s[i-1]2.2 状态转移方程情况1s[i-1] (dp[i] dp[i-2] 2 // 直接形成一对新括号情况2s[i-1] )if s[i - dp[i-1] - 1] (: dp[i] dp[i-1] 2 dp[i - dp[i-1] - 2]2.3 完整DP实现代码def longestValidParentheses(s: str) - int: n len(s) if n 0: return 0 dp [0] * n max_len 0 for i in range(1, n): if s[i] ): if s[i-1] (: dp[i] (dp[i-2] if i 2 else 0) 2 else: if i - dp[i-1] 0 and s[i - dp[i-1] - 1] (: dp[i] dp[i-1] 2 (dp[i - dp[i-1] - 2] if (i - dp[i-1]) 2 else 0) max_len max(max_len, dp[i]) return max_len2.4 DP解法复杂度分析时间复杂度O(n) —— 单次遍历字符串 空间复杂度O(n) —— 需要维护dp数组3. 栈解法详解3.1 栈解法核心思想利用栈存储索引而不是字符保持栈底元素为最后一个未匹配的右括号索引初始时栈中压入-1作为哨兵遇到(压入当前索引遇到)弹出栈顶计算当前索引与栈顶的差值3.2 栈解法实现代码def longestValidParentheses(s: str) - int: stack [-1] max_len 0 for i in range(len(s)): if s[i] (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: max_len max(max_len, i - stack[-1]) return max_len3.3 栈解法复杂度分析时间复杂度O(n) —— 单次遍历 空间复杂度O(n) —— 最坏情况下栈大小与字符串长度相同4. 最优解双指针法4.1 双指针法核心思路通过左右两次遍历统计有效括号长度从左到右遍历统计左右括号计数当left right时更新max_len当right left时重置计数从右到左遍历处理左括号多于右括号的情况4.2 双指针法实现代码def longestValidParentheses(s: str) - int: left right max_len 0 n len(s) # 从左到右扫描 for i in range(n): if s[i] (: left 1 else: right 1 if left right: max_len max(max_len, 2 * right) elif right left: left right 0 left right 0 # 从右到左扫描 for i in range(n-1, -1, -1): if s[i] (: left 1 else: right 1 if left right: max_len max(max_len, 2 * left) elif left right: left right 0 return max_len4.3 复杂度分析时间复杂度O(n) —— 两次遍历 空间复杂度O(1) —— 仅使用常数空间5. 解法对比与选择建议解法时间复杂度空间复杂度适用场景动态规划O(n)O(n)需要详细状态记录时栈O(n)O(n)需要处理嵌套结构时双指针O(n)O(1)内存受限时优先选择实际面试中推荐使用栈解法因为代码简洁直观容易解释思路处理复杂括号问题时扩展性强6. 常见错误与调试技巧6.1 边界条件处理常见错误忘记处理空字符串情况索引越界如dp[i-2]当i1时哨兵值设置不当栈解法中初始-1调试方法用简单测试用例验证如(), )(, ()()打印中间状态dp数组或栈内容6.2 特殊测试用例需要特别注意的测试用例 → 0(() → 2)()()) → 4()(() → 2((()))()) → 86.3 性能优化技巧提前终止当剩余字符数 ≤ 当前max_len时可提前结束空间优化双指针法空间最优并行处理对于超长字符串可考虑分段处理7. 题目变种与扩展7.1 变种题目统计所有有效括号子串数量LeetCode 678包含通配符的括号验证LeetCode 678生成所有有效括号组合LeetCode 227.2 实际应用场景代码语法检查括号匹配验证配置文件解析嵌套结构处理数学表达式求值我在实际刷题中发现这类括号问题有通用解题模式栈适合处理嵌套结构DP适合处理最优子结构问题双指针适合处理对称性问题对于面试准备建议重点掌握栈解法并理解如何从暴力解法逐步优化到最优解的过程。这类问题的核心在于发现括号匹配的规律性将全局问题分解为局部子问题求解。
1. 题目解析与核心思路Longest Valid Parentheses最长有效括号是LeetCode上的一道经典动态规划/栈应用题目编号32难度等级为Hard。题目要求在一个仅包含(和)的字符串中找出最长的有效括号子串的长度。有效括号子串需要满足所有括号都能正确匹配闭合。1.1 问题定义与示例分析有效括号子串的判定标准每个左括号(必须有对应的右括号)匹配匹配的括号对必须正确嵌套不能交叉示例分析 输入)()()) 输出4 解释最长有效子串是()()1.2 暴力解法与复杂度分析最直观的解法是检查所有可能的子串是否有效生成所有可能的子串O(n^2)个子串对每个子串检查有效性O(n)时间记录最大有效长度时间复杂度O(n^3) —— 对于n3×10^4的字符串完全不可行2. 动态规划解法详解2.1 DP状态定义定义dp[i]表示以s[i]结尾的最长有效括号子串长度。关键观察点只有)能形成有效子串的结尾对于s[i])需要考察前一个字符s[i-1]2.2 状态转移方程情况1s[i-1] (dp[i] dp[i-2] 2 // 直接形成一对新括号情况2s[i-1] )if s[i - dp[i-1] - 1] (: dp[i] dp[i-1] 2 dp[i - dp[i-1] - 2]2.3 完整DP实现代码def longestValidParentheses(s: str) - int: n len(s) if n 0: return 0 dp [0] * n max_len 0 for i in range(1, n): if s[i] ): if s[i-1] (: dp[i] (dp[i-2] if i 2 else 0) 2 else: if i - dp[i-1] 0 and s[i - dp[i-1] - 1] (: dp[i] dp[i-1] 2 (dp[i - dp[i-1] - 2] if (i - dp[i-1]) 2 else 0) max_len max(max_len, dp[i]) return max_len2.4 DP解法复杂度分析时间复杂度O(n) —— 单次遍历字符串 空间复杂度O(n) —— 需要维护dp数组3. 栈解法详解3.1 栈解法核心思想利用栈存储索引而不是字符保持栈底元素为最后一个未匹配的右括号索引初始时栈中压入-1作为哨兵遇到(压入当前索引遇到)弹出栈顶计算当前索引与栈顶的差值3.2 栈解法实现代码def longestValidParentheses(s: str) - int: stack [-1] max_len 0 for i in range(len(s)): if s[i] (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: max_len max(max_len, i - stack[-1]) return max_len3.3 栈解法复杂度分析时间复杂度O(n) —— 单次遍历 空间复杂度O(n) —— 最坏情况下栈大小与字符串长度相同4. 最优解双指针法4.1 双指针法核心思路通过左右两次遍历统计有效括号长度从左到右遍历统计左右括号计数当left right时更新max_len当right left时重置计数从右到左遍历处理左括号多于右括号的情况4.2 双指针法实现代码def longestValidParentheses(s: str) - int: left right max_len 0 n len(s) # 从左到右扫描 for i in range(n): if s[i] (: left 1 else: right 1 if left right: max_len max(max_len, 2 * right) elif right left: left right 0 left right 0 # 从右到左扫描 for i in range(n-1, -1, -1): if s[i] (: left 1 else: right 1 if left right: max_len max(max_len, 2 * left) elif left right: left right 0 return max_len4.3 复杂度分析时间复杂度O(n) —— 两次遍历 空间复杂度O(1) —— 仅使用常数空间5. 解法对比与选择建议解法时间复杂度空间复杂度适用场景动态规划O(n)O(n)需要详细状态记录时栈O(n)O(n)需要处理嵌套结构时双指针O(n)O(1)内存受限时优先选择实际面试中推荐使用栈解法因为代码简洁直观容易解释思路处理复杂括号问题时扩展性强6. 常见错误与调试技巧6.1 边界条件处理常见错误忘记处理空字符串情况索引越界如dp[i-2]当i1时哨兵值设置不当栈解法中初始-1调试方法用简单测试用例验证如(), )(, ()()打印中间状态dp数组或栈内容6.2 特殊测试用例需要特别注意的测试用例 → 0(() → 2)()()) → 4()(() → 2((()))()) → 86.3 性能优化技巧提前终止当剩余字符数 ≤ 当前max_len时可提前结束空间优化双指针法空间最优并行处理对于超长字符串可考虑分段处理7. 题目变种与扩展7.1 变种题目统计所有有效括号子串数量LeetCode 678包含通配符的括号验证LeetCode 678生成所有有效括号组合LeetCode 227.2 实际应用场景代码语法检查括号匹配验证配置文件解析嵌套结构处理数学表达式求值我在实际刷题中发现这类括号问题有通用解题模式栈适合处理嵌套结构DP适合处理最优子结构问题双指针适合处理对称性问题对于面试准备建议重点掌握栈解法并理解如何从暴力解法逐步优化到最优解的过程。这类问题的核心在于发现括号匹配的规律性将全局问题分解为局部子问题求解。
