32.LongestValidParentheses题目来源：力扣(LeetCode)https://leetcode-cn.com/problems/longest-valid-parentheses给定一个只包含'('和')'的题目，找出包含valid的最长子串的长度括号。示例1：输入：“(()”输出：2解释：最长的有效括号子串是“()”示例2：输入：“)()())”输出：4解释：最长的有效括号子串思路解决“()()”问题的方法：在栈问题中，要找到有效的括号，可能需要从内向外展开，这符合栈优先的特点进然后出。让我们先使用暴力解决方案来尝试解决这个问题。有效的括号是成对出现的，所以我们尝试列出所有可能的非空偶数长度子串来判断它们是否有效。遇到左括号(，就入栈。遇到右括号，弹出一个左括号(，如果栈中没有左括号，或者遍历完后栈中还有元素完成则此子串无效循环遍历更新最大长度具体代码如下：deflongestValidParentheses(self,s:str)->int:defis_valid(s):stack=[]foriinrange(len(s)):ifs[i]=='(':stack.append('(')elifstackandstack[-1]=='(':stack.pop()else:returnFalsereturnnotstackmax_len=0foriinrange(len(s)):forjinrange(i+2,len(s)+1,2):ifis_valid(s[i:j]):max_len=max(max_len,j-i)returnmax_len但是这里最后的执行结果是超时了。因为我们的方法是从字符串中列出所有可能的非空偶数子串，这里需要的时间复杂度是O(n^2)，这里我们尝试优化，上面的暴力解决方案是先列出所有可能的子串。这里，我们在遍历过程中直接判断遍历的子串是否合法，同时保持最大长度，这里有一点需要注意，一开始我们需要先-1入栈（后面解释）。具体实现方法如下：遇到(，将其索引压入t他堆叠；遇到),弹出栈顶元素，计算有效长度，循环遍历，保持最大长度。第二步，计算有效长度。这里直接用当前遍历字符的索引减去栈顶元素的索引。此时栈顶的索引对应：有效子串Value的前一个字符的索引，用例1来说明："(()"按照前面的方法，实现过程如下（stack代表栈，i是遍历时的索引值）：先把-1压入栈，然后stack=[-1]。开始遍历，先遇到(，将索引压入栈，stack=[-1,0],i=0；继续遍历，或者(，将索引压入栈，stack=[-1,0,1],i=1;最后遇到的是),弹出栈顶元素,stack=[-1,0],i=2,此时计算最大有效长度:当前字符索引减去栈顶元素的索引，也就是len=2-0。此时栈顶元素0就是第一个（第一个左括号）对应的索引。至于为什么要把-1压入栈中先入栈，这里举例说明："()"如果遇到这样的字符串，那么按照上面的实现过程，遍历结束，栈为空。那么计算最大有效长度就是错了，如果提前把-1压入栈中，那么此时栈中的元素就是stack=[-1]，那么这里就可以计算出结果了，再比如：这个字符串中的")()"，如果冷杉st遇到的是)，那么需要先进行入栈操作，这里如果入栈没有元素，这里也会报错。具体实现代码如下。代码实现类Solution:deflongestValidParentheses(self,s:str)->int:max_len=0stack=[]#当第一次遇到`)`时，需要先弹出元素，这里可以防止报错#当遇到`()`字符计数时，-1起到计算长度的作用stack.append(-1)foriinrange(len(s)):ifs[i]=='(':stack.append(i)else:stack.pop()ifnotstack:stack.append(i)else:max_len=max(max_len,i-stack[-1])returnmax_lenimplementationresultsummary因为要找出有效的括号，可能会遇到Brackets由内向外展开，类似于栈的先进后出特性，可以考虑用stack的方法解决；先用bruteforce的方法尝试解决问题。这里列出所有非空的偶数子串，并检查Itseffectiveness，统计最大有效长度（但执行后发现超时）。这里优化了暴力破解，得到不使用列表方法。遍历字符串时，检查遍历扫描的子串是否有效，计算的长度是否有效，具体方法如下：先将-1压入栈中（具体原因前面已经分析过），当遇到(,其索引入栈，遇到)，出栈，计算有效长度（此时用当前遍历的字符索引减去栈顶元素）。循环得到最大有效长度。文章原创，如果觉得写的不错，请关注点赞。微信公众号《书所集录》同步更新，也欢迎关注点赞。
