1. 题目描述
- 来源：力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
1
2
3
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
1
2
输入：s = ""
输出：0
提示：
1
2
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
2. 题解
2.1 个人思路
（比较菜，非官方题解，官方题解更🐂🍺，复杂度更低）
思路: 涉及到括号匹配，第一反应就是使用 栈 ，遍历字符串，左括号(则入栈，右括号)则判断是否能匹配并出栈一个左括号(，这样可以很简单的找出来输入字符串中有多少对能够匹配上的括号。但是，题目要求的是找出 最长有效（格式正确且连续）括号子串的长度，只找出能够匹配的括号对数是没办法保证它们之间是连续的。
- 例如：对于字符串
"(()(()"，通过入栈出栈操作，我们可以得到该字符串中有2对能够匹配的括号，但是2对括号之间并不连续，因此实际的最长有效括号子串的长度为2而不是4。
那么如何在找到的匹配括号对的基础上，去计算真正的最长有效括号子串长度呢？通过判断它们是否连续即可！
- 继续以字符串
"(()(()"为例，找到的两对括号位置为[[1, 2], [4, 5]]，它们之间少了个3，因此并不连续（被分成了2个块），所以不能计算整体的长度，而应该选择2个块中长度较长者作为输出。
2.2 算法流程
- 创建两个栈，命名为
stack_left和stack_right，分别用来存储左括号信息和匹配到的完整括号信息； - 遍历输入字符串，如果当前字符为左括号
(，则将其下标推入stack_left；如果当前字符为右括号)，则判断stack_left中是否为空，如不为空，则出栈一个左括号(的下标，并将匹配到的左右括号的下标都推入stack_right；如果stack_left为空，则丢弃改字符，继续循环； - 遍历完成之后，我们得到了包含所有匹配完整的括号的下标信息
stack_right，对其中的下标按照升序进行排序（时间复杂度不够低的原因）；然后遍历排序后的stack_right，查找断点（即计算每一个连续块的子串长度），获取最长有效括号子串长度（从每个连续块子串长度中选择最长的作为输出）。
3. 代码实现
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
def longestValidParentheses(self, s: str) -> int:
# 使用 栈 进行判断？
stack_left = []
stack_right = []
for idx, c in enumerate(s):
if c == '(':
# 左括号: 入栈
stack_left.append(idx)
continue
else:
# 右括号: 判断栈中是否存在与之匹配的左括号，存在则 tmp_len + 2，并出栈一个左括号
# 否则判断 max_len 与 tmp_len 的大小，并重置 tmp_len = 0
if len(stack_left) != 0:
# stack_right.append([stack_left[-1], idx])
stack_right.append(stack_left[-1])
stack_right.append(idx)
stack_left.pop()
# 排序
stack_right.sort()
if len(stack_right) == 0:
return 0
# 断点
max_len = 0
tmp_len = 1
for i in range(1, len(stack_right)):
if stack_right[i] - stack_right[i-1] == 1:
tmp_len += 1
else:
max_len = max(max_len, tmp_len)
tmp_len = 1
max_len = max(max_len, tmp_len)
return max_len
C++ 我又没写！