《Leetcode》32. 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

1、题目分析

其实就是找到最长括号，所谓最长的括号一定是一对一对的。比如（）（）or（（（））），所以本质就是一个配对题，看能配的对数最长是多少。

2、解题分析

利用栈去进行操作，可以初始化一个栈第一个元素是-1，这个-1的作用有两个：①作为一个标志位②为了入栈的元素是右括号

如果是左括号直接入栈如果是右括号且栈的长度是大于1的，执行出栈操作，并且更新最大值。当前值=右括号的下标-最近的左括号左边的下标否则就把stack[0]=i，这就说明栈为空了，而且入栈的元素是右括号了，从这个地方开始要重新进行划分了，所以最长的子串都是从0开始的。这也说明了-1的作用，就是假设-1为是右括号。

3、代码

class Solution: def longestValidParentheses(self, s: str) -> int: ans=0 # 最大合法长度(返回值) stack=[-1,] # stack[0]:合法括号起点-1 ; stack[1:]尚未匹配左括号下标 for i,ch in enumerate(s): if '('==ch: # 左括号 stack.append(i) elif len(stack)>1: # 右括号，且有成对左括号 stack.pop() # 成对匹配 #计算最大值 ans = max(ans, i - stack[-1]) else: # 非法的右括号 stack[0]=i return ans

总结：这个-1的设置对于边界值还是比较巧妙的，此题还有动态规划的方法没太看明白。