-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_42.java
More file actions
47 lines (43 loc) · 1.34 KB
/
Copy pathP_42.java
File metadata and controls
47 lines (43 loc) · 1.34 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
package leetcode.hard;
import java.util.ArrayDeque;
import java.util.Deque;
public class P_42 {
public int trapStack(int[] height) {
final Deque<Integer> dq = new ArrayDeque<>();
final int n = height.length;
int res = 0;
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && height[i] > height[dq.getFirst()]) {
final int prev = dq.removeFirst();
if (!dq.isEmpty()) {
final int minH = Math.min(height[dq.getFirst()], height[i]);
res += (minH - height[prev]) * (i - dq.getFirst() - 1);
}
}
dq.addFirst(i);
}
return res;
}
public static int trap(int[] height) {
int res = 0, start = 0, end = height.length - 1;
int mL = 0, mR = 0;
while (start < end) {
if (height[start] < height[end]) {
if (height[start] >= mL) {
mL = height[start];
} else {
res += mL - height[start];
}
start++;
} else {
if (height[end] >= mR) {
mR = height[end];
} else {
res += mR - height[end];
}
end--;
}
}
return res;
}
}