32.最长有效括号
难度：困难
题目
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
提示：
- 0 <= s.length <= 3 * 10 ^ 4
- s[i] 为 '(' 或 ')'
示例
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
分析
这道题我们使用三种解法分析解题：
暴力法思路
- 既然我们要找满足匹配规则的子串，那肯定要以左括号"("开始进行查找啊对吧？
- 我们遍历s，找多稍有左括号的下标保存成一个数组nums。
- 这时，如果数组长度等于s,那return 0即可。
- 下来我们开始循环nums，从每一个左括号开始进行查找
- 如果left == right的数量比较最大值ret=max(ret,left * 2)
-
如果right > left，停止，从下一个左括号下标继续找起。
时间复杂度O(n ^ 2),空间复杂度由于要存储left所有下标，所以最大为O(n)。
最终Python 8000ms，压线通关。
栈操作
之前说过遇到括号匹配，直接上栈，没毛病。这道题也是一样的。
- 初始栈为stack = [-1]即哨兵节点，这个是老套路...
- 然后开始遍历s的下标
- 当s[i]为左括号时，无脑入栈
- 当s[i]为右括号时
- 我们先pop栈顶
- 如果栈为空，则我们将哨兵pop掉了，没有正确匹配，将当前的i压栈继续当哨兵。
- 当pop出的栈顶为左括号，那么更新ret = max(ret, i- 此时栈顶)
- 重复3、4操作，即可获取最终结果
贪心思路
下面谈谈贪心思路，其实暴力解法通过的时候，我们就该考虑贪心的，因为我们做了很多重复的查找。
当我们发现右括号大于左括号的时候，我们break后，就可以从当前位置开始找下一个左括号了。
所以利用贪心，我们通过边循环变更新的思路，可以减少重复的查找。
- 初始left = right = 0，然后循环s
- 当left == right，更新ret
- 当right > left,那前面的数据都是报废且计算过最大值得，全部舍弃掉，重复1操作。
这样就完了吗？不是，我们只判断了right > left,那如果left一直大于right呢？
换位思考是不颠倒左右括号就能实现这种异常场景...
所以，我们从右向左再遍历一次s，就能解决这个问题了。
这里有个小tips，从左向右，从右向左，代码都是一样的，知识判断r > l 和 l > r的条件不一样。
有什么办法能复用这套查找代码呢？ 我们定义一个标记位，然后使用异或的判断就行。
公式为：order ^ (left > right)
初始order = True代表正序，然后计算left > right，
异或中True ^ True为False。只有当True ^ False时才为True，执行重置
倒序遍历时一样，order = False 但是left > right 一直是False，False ^ False为False。
这样就能实现代码的复用了，这个操作是不是很骚？
下来分别看看解题吧。
暴力解题
class Solution:
def longestValidParentheses(self, s: str) -> int:
lg = len(s)
nums = [i for i in range(lg) if s[i] == '(']
if len(nums) == lg:
return 0
ret = 0
for left in nums:
a, b = 0, 0
for i in range(left, lg):
if s[i] == '(':
a += 1
else:
b += 1
if a == b:
ret = max(ret, a * 2)
elif b > a:
break
return ret
栈解法
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1]
ret = 0
lg = len(s)
for i in range(lg):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
ret = max(ret, i - stack[-1])
return ret
贪心解题
class Solution:
def longestValidParentheses(self, s: str) -> int:
def comp(strings, order=True):
ret = 0
left = right = 0
for i in strings:
if i == '(':
left += 1
else:
right += 1
if left == right:
ret = max(ret, left * 2)
elif order ^ (left > right):
left = right = 0
return ret
return max(comp(s), comp(s[::-1], False))
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
