forked from algorithm024/algorithm024
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongestValidParentheses.java
More file actions
64 lines (61 loc) · 1.96 KB
/
LongestValidParentheses.java
File metadata and controls
64 lines (61 loc) · 1.96 KB
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
/**
* 32. 最长有效括号
* https://leetcode-cn.com/problems/longest-valid-parentheses/
*
* 方式一：栈
* 对于遇到的每个 '(' ，我们将它的下标放入栈中
* 对于遇到的每个 ')' ，我们先弹出栈顶元素表示匹配了当前右括号：
* 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
* 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
*
*
*
*/
class Solution {
public int longestValidParentheses(String s) {
int res = 0;
Deque<Integer> stack = new ArrayDeque<>();
// 最后一个没有被匹配的右括号的下标，为保持一致保存 -1
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 {
res = Math.max(res, i - stack.peek());
}
}
}
return res;
}
}
/**
* 方式二：动态规划
*
* DP方程
*
* dp[i]=dp[i−2]+2
*
* dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2
*
*/
public class Solution {
public int longestValidParentheses(String s) {
int res = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
res = Math.max(res, dp[i]);
}
}
return res;
}
}