LeetCode 32最长有效括号 | 栈与动态规划引言最长有效括号Longest Valid Parentheses是 LeetCode 第 32 题难度为 Hard。题目要求在只包含 ( 和 ) 的字符串中找到最长有效括号子串的长度。有效括号要求左右括号正确匹配。算法实现栈方法def longestValidParentheses(s): max_len 0 stack [-1] for i, c in enumerate(s): if c (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: max_len max(max_len, i - stack[-1]) return max_len动态规划方法def longestValidParentheses_dp(s): n len(s) 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 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_len max(max_len, dp[i]) return max_len复杂度分析时间复杂度O(n)空间复杂度O(n)总结最长有效括号问题可以用栈或动态规划解决。栈方法维护未匹配括号的索引动态规划记录以每个位置结尾的最长有效括号长度。
