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 bars, those bars can make up a container.
The most important thing is that how much water the container can trap has nothing to do with later bars.
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
0height0 - Water = 0
Storage:
+--+
0 [INDEX]
- Bar
1height1 - containWater(Bar
0.. Bar1) = 0 - Remove bars(Bar
0) no longer needed - Water = Water + 0
- Save Bar
1
Storage:
+--+
| |
+--+
1 [INDEX]
- Bar
2height0 Not meet the requirement to call
containWater(new bar's height0< saved bar's height1)Bar
3height2It is time to call
containWatercontainWater(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
7is 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 }