1，问题描述
32. 最长有效括号
难度：困难
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
1
2
3
| 输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
|
示例 2：
1
2
3
| 输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
|
示例 3：
提示：
0 <= s.length <= 3 * 104s[i] 为 '(' 或 ')'
2，初步思考
解法主要有3种，我首先想到的是栈stack的解决方案，因为之前有一个类似的题目
动态规划、正向逆向结合的解法是看了官方题解想明白的，
3，代码处理
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| import java.util.Deque;
import java.util.LinkedList;
public class _32最长有效括号 {
public int longestValidParentheses_combine(String s) {
int max = 0, left = 0, right = 0, index = 0;
char[] charArray = s.toCharArray();
while (index < charArray.length) {
if (charArray[index] == '(') {
left++;
} else {
right++;
}
if (left == right) {
max = Math.max(max, left);
} else if (right > left) {
left = 0;
right = 0;
}
index++;
}
left = 0;
right = 0;
index = charArray.length - 1;
while (index >= 0) {
if (charArray[index] == '(') {
left++;
} else {
right++;
}
if (left == right) {
max = Math.max(max, left);
} else if (right < left) {
left = 0;
right = 0;
}
index--;
}
return max * 2;
}
public int longestValidParentheses_dp(String s) {
int[] dp = new int[s.length()];
char[] charArray = s.toCharArray();
int max = 0;
for (int i = 1; i < charArray.length; i++) {
if (charArray[i] == ')') {
if (charArray[i - 1] == '(') {
dp[i] = 2 + (i - 2 >= 0 ? dp[i - 2] : 0);
} else if (i - dp[i - 1] - 1 >= 0 && charArray[i - dp[i - 1] - 1] == '(') {
dp[i] = 2 + dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
public int longestValidParentheses_stack_gov(String s) {
int max = 0;
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
max = Math.max(max, i - stack.peek());
}
}
}
return max;
}
public int longestValidParentheses_stack(String s) {
Deque<Pair> stack = new LinkedList<>();
char[] charArray = s.toCharArray();
boolean[] visited = new boolean[charArray.length];
for (int i = 0; i < charArray.length; i++) {
if (!stack.isEmpty() && stack.getLast().val == '(' && charArray[i] == ')') {
Pair pair = stack.pollLast();
visited[i] = true;
visited[pair.index] = true;
} else {
stack.offer(new Pair(charArray[i], i));
}
}
int max = 0;
int index = 0;
int counter = 0;
while (index < visited.length) {
if (!visited[index]) {
index++;
counter = 0;
} else {
counter++;
index++;
max = Math.max(max, counter);
}
}
return max;
}
static class Pair {
Character val;
int index;
public Pair(Character val, int index) {
this.val = val;
this.index = index;
}
}
public static void main(String[] args) {
_32最长有效括号 longestValidParentheses = new _32最长有效括号();
System.out.println(longestValidParentheses.longestValidParentheses_combine("(()"));
}
}
|