Trapping Rain Water
heights=[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
1public int trap(int[] heights) {
2 int left = 0;
3 int right = heights.length - 1;
4 int leftMax = 0;
5 int rightMax = 0;
6 int water = 0;
7
8 while (left < right) {
9 if (heights[left] < heights[right]) {
10 if (heights[left] >= leftMax) {
11 leftMax = heights[left];
12 } else {
13 water += leftMax - heights[left];
14 }
15 left++;
16 } else {
17 if (heights[right] >= rightMax) {
18 rightMax = heights[right];
19 } else {
20 water += rightMax - heights[right];
21 }
22 right--;
23 }
24 }
25
26 return water;
27}