/
main.go
80 lines (69 loc) · 1.37 KB
/
main.go
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
package _go
import "container/list"
/*
{
from:"https://leetcode-cn.com/problems/longest-valid-parentheses",
reference:[],
description:"最长有效括号长度",
solved:true,
}
*/
/*
1.额外维护一个相同长度的bool数组,保存相应位置括号是否已经被匹配,初始全部为false,
从左到右将括号带着位置一起入栈,一旦完成匹配,出栈并且将相应位置的bool数组设为true
最后扫描一遍bool数组,获取最长有效长度,时间复杂度O(n)
tips:使用container/list 表示栈
*/
type Item struct {
Pos int
Left bool //(
}
func longestValidParentheses(s string) int {
len := len(s)
if len == 0 || len == 1 {
return 0
}
valid := make([]bool, len) //false
var stack = list.New()
for i := 0; i < len; i++ {
if stack.Len() == 0 {
var left = true
if s[i] == ')' {
left = false
}
stack.PushBack(Item{
Pos: i,
Left: left,
})
} else {
var last = stack.Back().Value.(Item)
if s[i] == ')' && last.Left {
valid[i] = true
valid[last.Pos] = true
stack.Remove(stack.Back())
} else {
var left = true
if s[i] == ')' {
left = false
}
stack.PushBack(Item{
Pos: i,
Left: left,
})
}
}
}
var max = 0
var cur = 0
for i := 0; i < len; i++ {
if valid[i] {
cur++
if cur > max {
max = cur
}
} else {
cur = 0
}
}
return max
}