题目链接：https://leetcode.cn/problems/longest-valid-parentheses/
思路
前提：题目肯定存在有效括号子串
1.学过数据结构的课程，肯定知道堆栈里面的经典题括号匹配，这题就是括号匹配的进化版，这题依旧可以用堆栈来记录’ ( ‘的位置，用mark数组来记录每次堆栈为空的位置。
2.左边出现多余的括号, ‘ ) ’我们不用担心，我们已经算匹配完，用mark记录就行，‘ ( ’的话我们只需要先记录在堆栈里，再循环结束后，将多余的没有匹配的’ ( '一一用mark记录
3.右边出现多余的括号，‘)‘我们也不用担心，跟2是一样的思想，在这之前肯定已经多余的，我们只需要mark记录，’ ( '我们也不需要管，记录在堆栈里，循环结束后再用mark记录
4.我们只需要贪心的用’ ) ‘匹配’ ( '不用管他是怎么样的序列。
代码实现
func longestValidParentheses(s string) int { n := len(s) st := make([]int, 0, n) mark := make([]int, n) for i := range s{ if s[i] == '(' { st = append(st, i) }else{ //标记出连续匹配完的位置 if len(st) == 0{ mark[i] = 1 }else{ st = st[:len(st) - 1] } } } //把没有匹配的(全部上标记 for len(st) != 0{ mark[st[len(st) - 1]] = 1 st = st[:len(st) - 1] } len, ans := 0, 0 for i := range s{ if mark[i] == 1{ len = 0 continue } len++ if len > ans{ ans = len } } return ans }
