老卫带你学---leetcode刷题(32. 最长有效括号)

32. 最长有效括号

问题：

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
1
2
3
4
5

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
1
2
3
4
5

示例 3：

输入：s = ""
输出：0
1
2
3
4

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
1
2
3
4

解决：

这道题可以用栈，也可以用dp来做（dp不如栈清晰）
之前的括号类型的问题都采用的栈的处理思想，这道题也一样

stack栈维护当前括号处理序号，通过每次压栈/推栈来计算i-stack[-1]作为有效长度

func longestValidParentheses(s string) int {
	res := 0
	var stack []int
	stack = append(stack, -1) //避免pop时栈溢出
	for i := range s{
		if s[i]=='('{
			stack = append(stack, i)
		} else{
			stack=stack[:len(stack)-1]
			if len(stack)==0{
				stack = append(stack, i)
			} else{
				res = max(res,i-stack[len(stack)-1])
			}
		}
	}
	return res
}
func max(i,j int) int{
	if i>j{return i}
	return j
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res=0
        stack=[-1]
        for i in range(len(s)):
            if s[i]=='(':
                stack.append(i)
            else:
                stack=stack[:-1]
                if len(stack)==0:
                    stack.append(i)
                else:
                    res=max(res,i-stack[-1])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14