42. Trapping Rain Water

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.

http://www.geeksforgeeks.org/trapping-rain-water/

https://discuss.leetcode.com/topic/5125/sharing-my-simple-c-code-o-n-time-o-1-space

拿到题，先从最简单入手。

如何求能fill多少水？

1.对于每个位置而言，能不能fill？ -> 如果左右两边有比自己高的bar，那么可以fill

2.每个位置fill的水量：the heights of bars on left and right sides

因此可以对每个位置计算左右两边的最高height. -> Math.min(leftHeightest, rightHeightest) - height[i]

2.优化：

prre-compute highest bar on left and right of every bar in O(n) time.

An element of array can store water if there are higher bars on left and right. We can find amount of water to be stored in every element by finding the heights of bars on left and right sides. The idea is to compute amount of water that can be stored in every element of array. For example, consider the array {3, 0, 0, 2, 0, 4}, we can store two units of water at indexes 1 and 2, and one unit of water at index 2.

A Simple Solution is to traverse every array element and find the highest bars on left and right sides. Take the smaller of two heights. The difference between smaller height and height of current element is the amount of water that can be stored in this array element. Time complexity of this solution is O(n2).

An Efficient Solution is to prre-compute highest bar on left and right of every bar in O(n) time. Then use these pre-computed values to find the amount of water in every array element. 

int findWater(int arr[], int n)

{

    // left[i] contains height of tallest bar to the

    // left of i'th bar including itself

    int left[n];

    // Right [i] contains height of tallest bar to

    // the right of ith bar including itself

    int right[n];

    // Initialize result

    int water = 0;

    // Fill left array

    left[0] = arr[0];

    for (int i = 1; i < n; i++)

       left[i] = max(left[i-1], arr[i]);

    // Fill right array

    right[n-1] = arr[n-1];

    for (int i = n-2; i >= 0; i--)

       right[i] = max(right[i+1], arr[i]);

    // Calculate the accumulated water element by element

    // consider the amount of water on i'th bar, the

    // amount of water accumulated on this particular

    // bar will be equal to min(left[i], right[i]) - arr[i] .

    for (int i = 0; i < n; i++)

       water += min(left[i],right[i]) - arr[i];

    return water;

}

3。 再优化！

目标是找到 Math.min(leftHeightest, rightHeightest)

用两个指针可以知道两边最大的是谁。（类似contain most water／array变身二元一次方程那个题 的双指针思想）

那么维护左右两边最大值，在我们扫到i这位置的时候，需要知道左右两边最高的较小的那个。

如果每次移动小的那个位置的指针，并且记录最大值，那么到达i位置的时候，就知道左右两边最大值相比，较小的那个了！

class Solution {
public:
    int trap(int A[], int n) {
        int left=0; int right=n-1;
        int res=0;
        int maxleft=0, maxright=0;
        while(left<=right){
            if(A[left]<=A[right]){
                if(A[left]>=maxleft) maxleft=A[left];
                else res+=maxleft-A[left];
                left++;
            }
            else{
                if(A[right]>=maxright) maxright= A[right];
                else res+=maxright-A[right];
                right--;
            }
        }
        return res;
    }
};

4. 类似 Largest Rectangle in Histogram解法
用stack
维护一个单调递减的stack，因为递减的时候不能围城水槽，如果碰到增的地方，就会构成水槽。此时可以计算以stack.peek那个点为bottom，然后右boundary是当前指针的area。pop stack中比nums[i]小的点，因为这些点都可以构成水槽，并且水槽的boundary是stack中的peek和nums[i]较小的那一个。这样算的时候，计算的是(i-j)宽*(min(height[j],peek())-bottom)(高)。不是一个bin一个bin的计算，而是按照当前情况能围成的高度计算。如果实际上水槽能fill的高度大于当前计算的高度是不会影响结果的。因为这种情况左边和右边一定存在一个位置k，(i-k)宽*(min(height[k],peek())-前边算过的一个min)(高)

  public int trap(int[] height) {  
     int bottom = 0;  
     Stack < Integer> stack = new Stack<>();  
     int ret = 0, n = height.length;  
     if(n == 0) return 0;  
     for(int i =0; i < n; i++){  
       while(!stack.empty() && height[i] > height[stack.peek()]){  
         bottom = stack.pop();  
         if(stack.size()!=0)  
           ret += Math.max(0,  
             (Math.min(height[i] ,height[stack.peek()]) - height[bottom])*(i-stack.peek()-1));  
       }  
       if(stack.empty() || height[i] < height[stack.peek()]){  
         stack.push(i);  
       }  
       if(height[i] == height[stack.peek()]){stack.pop(); stack.push(i);}  
     }  
     return ret;  
   }