/
Solution.java
72 lines (47 loc) · 1.55 KB
/
Solution.java
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
public class Solution {
static class Bar{
int pos;
int height;
Bar(int pos, int height){
this.pos = pos;
this.height = height;
}
}
int containWater(Deque<Bar> queue){
Bar left = queue.peekFirst();
Bar right = queue.peekLast();
int water = 0;
if(right.height >= left.height){
water += Math.min(right.height, left.height) * (right.pos - left.pos - 1);
queue.removeFirst(); // remove left
// remove stones
while(queue.size() > 1){
water -= queue.removeFirst().height;
}
}
return water;
}
int[] reverseAndToInt(Deque<Bar> queue){
int[] a = new int[queue.size()];
int i = 0;
while(!queue.isEmpty()){
a[i++] = queue.removeLast().height;
}
return a;
}
public int trap(int[] A) {
if (A.length <= 2) return 0;
Deque<Bar> queue = new LinkedList<Bar>();
int s = 0;
while(s < A.length && A[s] == 0) s++;
if(s < A.length)
queue.add(new Bar(s, A[s]));
int water = 0;
for(int i = s + 1; i < A.length; i++){
queue.add(new Bar(i, A[i]));
water += containWater(queue);
}
water += trap(reverseAndToInt(queue));
return water;
}
}