作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
问题描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
这个问题可以通过几种不同的方法来解决，包括动态规划、栈和不使用额外空间的扫描法。
方法一：动态规划
动态规划是解决此类问题的一个非常直观的方法。我们可以定义一个 dp 数组，其中 dp[i] 表示以 s[i] 结尾的最长有效括号的长度。
实现步骤
- 初始化：创建一个长度为
n+1的数组dp，所有值初始化为 0。 - 状态转移：
- 如果
s[i]为')'且s[i-1]为'('，则dp[i] = dp[i-2] + 2。 - 如果
s[i]为')'且s[i-1]为')'且s[i-dp[i-1]-1]为'('，则dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2。
- 计算结果：最大值在
dp数组中取得。
代码示例
def longestValidParentheses(s): n = len(s) dp = [0] * (n + 1) max_length = 0 for i in range(1, n): if s[i] == ')': if s[i-1] == '(': dp[i] = dp[i-2] + 2 elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(': dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2 max_length = max(max_length, dp[i]) return max_length
方法二：栈
使用栈是另一种常见的解决方案，可以有效地追踪未匹配的括号。
实现步骤
- 初始化栈：栈中预先压入
-1，表示最后一个未匹配的右括号的位置。 - 遍历字符串：
- 如果
s[i]为'('，将i压栈。 - 如果
s[i]为')'：
- 弹出栈顶元素。
- 如果栈为空，将当前索引
i压栈。 - 如果栈不为空，更新结果
max_length = max(max_length, i - stack[-1])。
代码示例
def longestValidParentheses(s): max_length = 0 stack = [-1] for i in range(len(s)): if s[i] == '(': stack.append(i) else: stack.pop() if not stack: stack.append(i) else: max_length = max(max_length, i - stack[-1]) return max_length
方法三：不使用额外空间的扫描法
实现步骤
- 第一遍扫描（从左到右）:
- 初始化两个计数器：
left为左括号计数器，right为右括号计数器，初始化为0。 - 遍历字符串：对字符串
s的每一个字符进行遍历。
- 增加计数器：如果字符是
'('，增加left计数器；如果字符是')'，增加right计数器。 - 计算有效长度：
- 当
left计数器等于right计数器时，计算当前有效的括号长度，即2 * right（或2 * left，因为此时left == right），并更新最大长度maxlength。 - 如果
right计数器大于left计数器，说明括号已经无法闭合，需要重置两个计数器为0，重新开始计数。
- 第二遍扫描（从右到左）:
- 重新初始化计数器：同样，
left和right初始化为0，但此次遍历的目的是捕捉如(()这类左括号多于右括号的情况。 - 逆向遍历字符串：从字符串的最后一个字符向前遍历。
- 增加计数器：如果字符是
'('，增加left计数器；如果字符是')'，增加right计数器。 - 计算有效长度：
- 当
left计数器等于right计数器时，计算当前有效的括号长度，即2 * left，并更新最大长度maxlength。 - 如果
left计数器大于right计数器，说明左括号过多，括号无法闭合，需要重置两个计数器为0，重新开始计数。
代码示例
def longestValidParentheses(s): left = right = maxlength = 0 # Left to right for char in s: if char == '(': left += 1 else: right += 1 if left == right: maxlength = max(maxlength, 2 * right) elif right > left: left = right = 0 left = right = 0 # Right to left for char in reversed(s): if char == '(': left += 1 else: right += 1 if left == right: maxlength = max(maxlength, 2 * left) elif left > right: left = right = 0 return maxlength
总结
选择哪种方法取决于具体的应用场景和空间时间的权衡：
- 如果内存资源不是问题，可以优先考虑使用 动态规划 或 栈 方法，因为它们易于实现和理解。
- 如果需要优化空间消耗，双向扫描 提供了一个不使用额外空间的有效解决方案。
以上分析展示了每种方法在解决 "最长有效括号" 问题时的性能和适用性，可以根据实际需求灵活选择最合适的方法。
欢迎关注微信公众号 数据分析螺丝钉
