LeetCode 最长合法括号子串题解题目描述给定一个只包含(和)的字符串找出最长有效连接连续子串的长度。示例输入s )()())输出4解题思路方法栈思路使用栈来解决这个问题。首先将 -1 压入栈中作为起始位置。遍历字符串对于每个字符如果是左括号将当前索引压入栈中。如果是右括号先弹出栈顶元素匹配左括号或起始位置。计算当前有效括号子串的长度并更新最大长度。返回最大长度。复杂度分析时间复杂度O(n)其中 n 是字符串的长度。空间复杂度O(n)需要额外的空间来存储栈。代码实现方法栈# 最长合法括号子串栈 def longest_valid_parentheses(s): max_length 0 stack [-1] for i, char in enumerate(s): if char (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: max_length max(max_length, i - stack[-1]) return max_length # 测试 def test_longest_valid_parentheses(): s )()()) print(longest_valid_parentheses(s)) # 输出4 s (() print(longest_valid_parentheses(s)) # 输出2 if __name__ __main__: test_longest_valid_parentheses()方法动态规划# 最长合法括号子串动态规划 def longest_valid_parentheses_dp(s): n len(s) if n 0: return 0 dp [0] * n max_length 0 for i in range(1, n): if s[i] ): if s[i-1] (: dp[i] dp[i-2] 2 if i 2 else 2 elif 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_length max(max_length, dp[i]) return max_length # 测试 def test_longest_valid_parentheses_dp(): s )()()) print(longest_valid_parentheses_dp(s)) # 输出4 if __name__ __main__: test_longest_valid_parentheses_dp()测试用例测试用例 1基本情况输入s )()())输出4测试用例 2括号配对输入s (()输出2总结最长合法括号子串是一个经典的栈和动态规划问题它可以通过栈或动态规划来高效地解决。栈方法的核心思想是将 -1 作为起始位置压入栈中遍历字符串匹配左右括号计算有效括号子串的长度。动态规划方法的核心思想是使用 DP 表存储以每个位置结尾的最长有效括号子串长度。掌握栈和动态规划的使用方法对于解决类似的问题非常重要。