3.2 Trapping Rain Water

Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. https://leetcode.com/problems/trapping-rain-water/

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Method

It is a wooden bucket theory that how much water a container can have depends on the shortest plank. When two elements and x-axis compose a container, how much the water it can contains is depends on the short one. Besides, in the container the bottom is not flat, so we can split the container in to small pieces.

Firstly, We need to find whether there is a container. We need to find two elements that they are higher than some elements between them.

Then we should split the container we find to calculate how much water it can has.

For method one:

Two pointers

Start from two end sides, move to the inner direction.

We move from the short one, because we already have two sides. When we move from the short one, if there has a lower element, it means that we can contains water in its difference of height between the short side with this element. But if we meet a higher plank, we can change one side of the original container we use. Because we move continuously, if the height of plank increasing continuously, we cannot have space to hold water.

So we can do this step repeatedly until the two pointers meet together where is also the highest plank of all planks.

for method two:

The basic theory of the question is the same, but we use a different data structure to implements process. It is stack.

Firstly, we push the start index into stack,and then move from the start to end, if we meet the lower plank than the peek plank in the stack, we push the index into stack. So the stack is monotone stack in which the elements are monotonically deceasing. So if we meet a plank higher than the peek one in the stack, we pop it from the stack, then it compose a small container, where the left side is the peek of stack, the right side is the new plank, so for this container the width is (index of new element - s.peek() - 1) * (math.min(s.peek(), new element) - s.pop());

we do it repeatedly until the stack doesn't has any elements that smaller than the new element, and then we push the new element in stack, and to next calculation.

the accumulated sum of the are is the water we can contains.

Time and Space Complexity

O(N)

Code

METHOD ONE:

  public int trap(int[] height) {
//      if (height == null || height.length <= 2){
//          return 0;
//      }

//      int sum = 0;
//      for (int i : height){
//          sum += i;
//      }

//      int left = 0;
//      int right = height.length - 1;

//      int leftHeight = height[left];
//      int rightHeight = height[right];

//      int total = 0;
//      while (left < right){
//           if (leftHeight < rightHeight){
//               int j = left + 1;
//               while (j < right && height[j] < leftHeight){
//                      int area = leftHeight - height[j];
//                      total += area;
//                      j++;
//               }
//               leftHeight = height[j];
//               left = j;
//           } else {
//               int j = right - 1;
//               while (j > left && height[j] < rightHeight){
//                      int area = rightHeight - height[j];
//                      total += area;
//                      j--;
//               }
//               rightHeight = height[j];
//               right = j;
//               } 
//     }

//     return total;

// }

METHOD TWO:

 public int trap(int[] height){
 Stack<Integer> s = new Stack<Integer>();
    s.push(0);

    int cur = 1;
    int total = 0;

    while (cur < height.length) {
         int curHeight = height[cur];
         while (!s.isEmpty() && curHeight >= height[s.peek()]){
               int he = height[s.pop()];
               if (s.isEmpty()){
                      break;
                } else {
                       int width = cur - s.peek() - 1;
                       int area = (Math.min(curHeight,height[s.peek()]) - he) * width;
                       total += area;
                }

         }
         s.push(cur);
         cur++;
    }

    return total; 

}