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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
package leetcode
/**
解题思路:
1. 利用括号成对的特性, 左右括号相等
有一个 `(` 那必然会有一个 `)` , 计左右括号出现的次数, 次数相等的算作一次合并
这个方法有局限性在如果出现 `(()` 这种情况单次遍历不能统计到,
作为弥补就需要正反两次遍历, 取最大值
时间复杂度 O(n), 空间复杂度 O(1)
2. 采取动态规划的求解方式
因为括号和套娃似的, 外层括号可以直接采用内层的处理结果, 不过要另建一个数组来缓存结果
创建缓存数组dp, 比如:
s = []string{"(", "(", ")", "(", ")", ")"}
dp = []int{0, 0, 2, 0, 4, 6}
在合法括号中左括号的下标和dp映射, 合法括号的长度为对应下标的元素值
那么上述例子中 下标3存在一个合法的括号, 长度为2, 这是 () 这种组合
下标为4存在一个合法括号, 这也是一个()组合, 但是不会计算第一个括号了, 直接到下标3拿计算结果
到下标5时, 存在 )) 这种组合, 那么已知下标4是有值的(代表是一个合法括号) 那么到下标5就直接往前推 4 个长度
得到下标 0 是 (, 下标5是 ), 括号成立, 因此内层括号+2 就是这个的括号长度
时间复杂度 O(n), 空间复杂度 O(n)
3. 使用栈
栈的特性是后进先出, 括号也有类似的特性, 因此可以这么搞
我们首先将 −1 放入栈顶。
对于遇到的每个 ( ，我们将它的下标放入栈中。
对于遇到的每个 ) ，我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。
时间复杂度 O(n), 空间复杂度 O(n)
作者：LeetCode
链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func longestValidParentheses(s string) int {
if len(s) < 2 {
return 0
}
left := byte('(')
var rCnt, lCnt, length int
for i := 0; i < len(s); i++ {
if s[i] == left {
lCnt++
} else {
rCnt++
}
if rCnt > lCnt { // 从左往右必死的情况
lCnt, rCnt = 0, 0
}
if rCnt == lCnt && rCnt*2 > length {
length = rCnt * 2
}
}
lCnt, rCnt = 0, 0
for i := len(s) - 1; i > 0; i-- {
if s[i] == left {
lCnt++
} else {
rCnt++
}
if rCnt < lCnt { // 从右往左必死的情况
lCnt, rCnt = 0, 0
}
if rCnt == lCnt && rCnt*2 > length {
length = rCnt * 2
}
}
return length
}
func longestValidParenthesesV2(s string) int {
if len(s) < 2 {
return 0
}
dp := make([]int, len(s))
left := byte('(')
right := byte(')')
for i := 1; i < len(s); i++ {
if s[i] == right {
if s[i-1] == left { // 如 () 这样的情况
if i >= 2 {
dp[i] = dp[i-2] + 2
} else {
dp[i] = 2
}
continue
}
pre := dp[i-1]
if (i-pre-1) >= 0 && s[i-1] == right { // 如 )) 这样的情况
if s[i-pre-1] == left {
dp[i] = dp[i-1] + 2
if i-dp[i] > 0 { // 如果存在紧挨着的两个合法组合, 就拼起来
dp[i] += dp[i-dp[i]]
}
}
}
}
}
// fmt.Printf("\n %#+v \n", dp)
var maxLen int
for i := 0; i < len(s); i++ {
if maxLen < dp[i] {
maxLen = dp[i]
}
}
return maxLen
}
|