Trapping Rain Water
Art
+--+
| |
+--+ | +--+ +--+
| |WW WW WW| | |WW| |
+--+ | +--+ +--+ | +--+ +--+
| |WW| | |WW| | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+
0 1 2 3 4 5 6 7 8 9 A B [INDEX]
Loop invariant with Stack/Queue
Sometimes, there may be an inconclusive result after a loop. you have to wait for one or more loop to merge them all to the final result.
loop
if can merge
merge and commit all pending data to result
else
save and wait
In this case, when a new bar
comes, if it is greater than or equals to all saved bar
s, those bar
s can make up a container.
The most important thing is that how much water the container can trap has nothing to do with later bar
s.
How much water, Bars and stones.
+--+
| |
+--+ | |
| |WW WW WW| |
| +--+ +--+ |
| | |WW| | |
+--+--+--+--+--+
3 4 5 6 7 [INDEX]
figure above show two bars with heights 2
and 3
.
so the container can trap MIN(2,3) * (7 - 3 - 1) = 6
.
but, wait, there are 2
stones (Bar 4
and Bar 6
) in the water, we should take them away. 6 - 2 = 4
.
// input bars are guaranteed that
// * there are more than 2 bars
// * first and last bar are the highest
function containWater(bars)
left = bars.first
right = bars.last
// container
water = MIN(left.height, right.height) * (right.pos - left.pos - 1)
// remove stone
foreach bar in bars without first and last
water = water - bar.height
return water
Animation
- Bar
0
height0
- Water = 0
Storage:
+--+
0 [INDEX]
- Bar
1
height1
- containWater(Bar
0
.. Bar1
) = 0 - Remove bars(Bar
0
) no longer needed - Water = Water + 0
- Save Bar
1
Storage:
+--+
| |
+--+
1 [INDEX]
- Bar
2
height0
Not meet the requirement to call
containWater
(new bar's height0
< saved bar's height1
)Bar
3
height2
It is time to call
containWater
containWater(Bar
1
.. Bar3
) = 1Water = Water + 1
+--+
| |
+--+ | |
| |WW| |
+--+--+--+
1 2 3 [INDEX]
- Save Bar
3
Storage:
+--+
| |
| |
| |
+--+
3 [INDEX]
- Deal with Bar
3
,4
,5
,6
- Not meet the requirement to call
containWater
- Save them
Storage:
+--+
| |
+--+ | |
| |WW WW WW| |
| +--+ +--+ |
| | |WW| | |
+--+--+--+--+--+
3 4 5 6 7 [INDEX]
- Bar
7
is the higher than any savedBar
, so callcontainWater
- containWater(Bar
3
.. Bar7
) = 4 - Water = Water + 4
Bars left in Storage
After the loop ends, there left some bars in the storage.
From the figure below, there is 1
water in left bars. but, no bar can trigger code to call containWater
.
Storage:
+--+
| |
| +--+ +--+
| | |WW| |
| | +--+ +--+
| | | | | |
+--+--+--+--+--+
7 8 9 A B [INDEX]
How much water these bar can trap has nothing to do with any other bars, so we can convert the storage to a familiar question.
Yes, just reverse it to a new one.
+--+
| |
+--+ +--+ |
| |WW| | |
+--+ +--+ | |
| | | | | |
+--+--+--+--+--+
0 1 2 3 4 [INDEX]
Now, add trap( new one ) to water
Source code Read on Github
1 public class Solution {
2
3 static class Bar{
4 int pos;
5 int height;
6
7 Bar(int pos, int height){
8 this.pos = pos;
9 this.height = height;
10 }
11 }
12
13 int containWater(Deque<Bar> queue){
14
15 Bar left = queue.peekFirst();
16 Bar right = queue.peekLast();
17
18 int water = 0;
19
20 if(right.height >= left.height){
21
22 water += Math.min(right.height, left.height) * (right.pos - left.pos - 1);
23
24 queue.removeFirst(); // remove left
25
26 // remove stones
27 while(queue.size() > 1){
28 water -= queue.removeFirst().height;
29 }
30 }
31
32 return water;
33 }
34
35 int[] reverseAndToInt(Deque<Bar> queue){
36 int[] a = new int[queue.size()];
37 int i = 0;
38
39 while(!queue.isEmpty()){
40 a[i++] = queue.removeLast().height;
41
42 }
43
44 return a;
45 }
46
47 public int trap(int[] A) {
48
49 if (A.length <= 2) return 0;
50
51 Deque<Bar> queue = new LinkedList<Bar>();
52
53 int s = 0;
54 while(s < A.length && A[s] == 0) s++;
55
56 if(s < A.length)
57 queue.add(new Bar(s, A[s]));
58
59 int water = 0;
60
61 for(int i = s + 1; i < A.length; i++){
62
63 queue.add(new Bar(i, A[i]));
64
65 water += containWater(queue);
66 }
67
68 water += trap(reverseAndToInt(queue));
69
70 return water;
71 }
72 }