LeetCode 42 - Trapping Rain Water


LeetCode 11 - Container With Most Water
LeetCode 42 - Trapping Rain Water
LeetCode 407 - Trapping Rain Water II
http://yucoding.blogspot.com/2013/05/leetcode-question-111-trapping-rain.html
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.
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!
TODO: http://www.cnblogs.com/grandyang/p/4402392.html
http://yucoding.blogspot.com/2013/05/leetcode-question-111-trapping-rain.html
An O(n) solution is to consider each bar at a time, we can see that, for each bar, the water itself can trap depends on the max height on its left and right, e.g. if current bar is of height 2, the max height on its left is 4, max height on its right is 3, then water can be trapped in this bar is min(4,3)-2 = 1.

Thus, we can scan the whole map twice to get the max height on right and left, respectively. Finally scan the map again to get the water trapped of all.
X.
http://wxx5433.github.io/trapping-rain-water.html
Instead of trying to find two bars and water trapped between them by using height * width, we try to find the water trapped in each bar. This can be achieved by figuring out the lowest bar that is higher than the this bar on both sides.
The first method is to use two auxiliary arrays to record the highest bar to the left and right side of each bar. Then for each bar, simply use the lower bar as the height and compute the water trapped if the current bar is lower than that height. Why can we do this? The reason is that if we can find higher bars on both side, then there must be water trapped on this bar: min(leftMax[i], rightMax[i]) - height[i].
  public int trap(int[] height) {
    int[] leftMax = new int[height.length];
    int[] rightMax = new int[height.length];
    // compute the highest bar on the left
    for (int i = 1; i < height.length; ++i) {
      leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
    }
    // compute the heighest bar on the right
    for (int i = height.length - 2; i >= 0; --i) {
      rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
    }
    // compute the trapped volume
    int volume = 0;
    for (int i = 1; i < height.length - 1; ++i) {
      int min = Math.min(leftMax[i], rightMax[i]);
      if (height[i] < min) {
        volume += min - height[i];
      }
    }

    return volume;
  }

X. Two Pointers
The second approach optimize the space usage by finding that instead of keeping two areas, it is sufficient to know there are two bars higher than this bar on two sides, and we can safely add the min(leftMax, rightMax) - height. We only need to keep one pointer on each side and moves the pointer with lower height each time. Before moving, we want to update leftMax/rightMax and if the current height is smaller than leftMax/rightMax, we want to add it to the water volume trapped. Why can we do this? Since the reason we want to move the pointer is that it is lower, and if the height is even lower, it must be trapped into these two bars.
  public int trap(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int leftMax = 0;
    int rightMax = 0;
    int volume = 0;
    while (left < right) {
      if (height[left] <= height[right]) {
        if (height[left] >= leftMax) {
          leftMax = height[left];
        } else {
          volume += leftMax - height[left];
        }
        ++left;
      } else {
        if (height[right] >= rightMax) {
          rightMax = height[right];
        } else {
          volume += rightMax - height[right];
        }
        --right;
      }
    }

    return volume;
  }
https://discuss.leetcode.com/topic/3016/share-my-short-solution
Keep track of the maximum height from both forward directions backward directions, call them leftmax and rightmax.
the volume always depends on the shorter bar.

I calculated the stored water at each index a and b in my code. At the start of every loop, I update the current maximum height from left side (that is from A[0,1...a]) and the maximum height from right side(from A[b,b+1...n-1]). if(leftmax<rightmax) then, at least (leftmax-A[a]) water can definitely be stored no matter what happens between [a,b] since we know there is a barrier at the rightside(rightmax>leftmax). On the other side, we cannot store more water than (leftmax-A[a]) at index a since the barrier at left is of height leftmax. So, we know the water that can be stored at index a is exactly (leftmax-A[a]). The same logic applies to the case when (leftmax>rightmax). At each loop we can make a and b one step closer. Thus we can finish it in linear time.
public int trap(int[] A){
    int a=0;
    int b=A.length-1;
    int max=0;
    int leftmax=0;
    int rightmax=0;
    while(a<=b){
        leftmax=Math.max(leftmax,A[a]);
        rightmax=Math.max(rightmax,A[b]);
        if(leftmax<rightmax){
            max+=(leftmax-A[a]);       // leftmax is smaller than rightmax, so the (leftmax-A[a]) water can be stored
            a++;
        }
        else{
            max+=(rightmax-A[b]);
            b--;
        }
    }
    return max;
}
http://blog.csdn.net/linhuanmars/article/details/20888505
这种方法是基于动态规划的，基本思路就是维护一个长度为n的数组，进行两次扫描，一次从左往右，一次从右往左。第一次扫描的时候维护对于每一个bar左边最大的高度是多少，存入数组对应元素中，第二次扫描的时候维护右边最大的高度，并且比较将左边和右边小的最大高度（我们成为瓶颈）存入数组对应元素中。这样两遍扫描之后就可以得到每一个bar能承受的最大水量，从而累加得出结果。这个方法只需要两次扫描，所以时间复杂度是O(2*n)=O(n)。空间上需要一个长度为n的数组，复杂度是O(n)
  1. public int trap(int[] A) {  
  2.     if(A==null || A.length==0)  
  3.         return 0;  
  4.     int max = 0;  
  5.     int res = 0;  
  6.     int[] container = new int[A.length];  
  7.     for(int i=0;i<A.length;i++)  
  8.     {  
  9.         container[i]=max;  
  10.         max = Math.max(max,A[i]);  
  11.     }  
  12.     max = 0;  
  13.     for(int i=A.length-1;i>=0;i--)  
  14.     {  
  15.         container[i] = Math.min(max,container[i]);  
  16.         max = Math.max(max,A[i]);  
  17.         res += container[i]-A[i]>0?container[i]-A[i]:0;  
  18.     }      
  19.     return res;  
  20. } 
https://discuss.leetcode.com/topic/4136/a-different-o-n-approach-easy-to-understand-and-simple-code/3
scan A both from left to right and right to left, record the largest seen during the scan; then for each position the water level should be the min of the 2 large value.
    if(A.length==0) return 0;

    int[] A1=new int[A.length];
    int[] A2=new int[A.length];
    int max=A[0];
    for(int i =0;i<A.length;i++) {
        if(A[i]>max) max=A[i];
        A1[i]=max;
    }
    max=A[A.length-1];
    for(int i=A.length-1;i>=0;i--){
        if(A[i]>max) max=A[i];
        A2[i]=max;
    }
    int sum=0;
    for(int i=0;i<A.length;i++){
     sum=sum+Math.min(A1[i],A2[i])-A[i];
    }
    return sum;
X.  http://www.wtoutiao.com/p/hadVnv.html
两个指针扫一遍， 这道题其实是一道两个指针的题目，而且指针属性是对撞型指针。 所以用两个指针分别指向数组的头和数组尾。 然后每次比较两个指针所指向的值，选小值指针向中间移动，并且每次更新遍历LeftMostHeight或者RightMostHeight， 这样就可以算出每个点的可以接的雨水数目

 这个方法算是一种常见的技巧，从两边各扫描一次得到我们需要维护的变量，通常适用于当前元素需要两边元素来决定的问题，非常类似的题目是Candy，有兴趣的朋友可以看看哈。
只需要一次扫描就能完成。基本思路是这样的，用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了，可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。这里能作为停下来判断的窗口，说明肯定比前面的大了，所以目前肯定装不了水（不然前面会直接扫过去）。这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了
这种两边往中间夹逼的方法也挺常用的，它的核心思路就是向中间夹逼时能确定接下来移动一侧窗口不可能使结果变得更好，所以每次能确定移动一侧指针，直到相遇为止。这种方法带有一些贪心，用到的有Two Sum，Container With Most Water，都是不错的题目
  1. public int trap(int[] A) {  
  2.     if(A==null || A.length ==0)  
  3.         return 0;  
  4.     int l = 0;  
  5.     int r = A.length-1;  
  6.     int res = 0;  
  7.     while(l<r)  
  8.     {  
  9.         int min = Math.min(A[l],A[r]);  
  10.         if(A[l] == min)  
  11.         {  
  12.             l++;  
  13.             while(l<r && A[l]<min)  
  14.             {  
  15.                 res += min-A[l];  
  16.                 l++;  
  17.             }  
  18.         }  
  19.         else  
  20.         {  
  21.             r--;  
  22.             while(l<r && A[r]<min)  
  23.             {  
  24.                 res += min-A[r];  
  25.                 r--;  
  26.             }  
  27.         }  
  28.     }  
  29.     return res;  
  30. } 


Space Optimization in above solution :
Instead of maintaing two arrays of size n for storing left and right max of each element, we will just maintain two variables to store the maximum till that point. Since water trapped at any element = min( max_left, max_right) – arr[i] we will calculate water trapped on smaller element out of A[lo] and A[hi] first and move the pointers till lo doesn’t cross hi.
    static int findWater(int arr[], int n)
    {
        // initialize output
        int result = 0;
           
        // maximum element on left and right
        int left_max = 0, right_max = 0;
           
        // indices to traverse the array
        int lo = 0, hi = n-1;
           
        while(lo <= hi) 
        {
            if(arr[lo] < arr[hi])
            {
                if(arr[lo] > left_max)
      
                // update max in left
                left_max = arr[lo];
                else
      
                // water on curr element = 
                // max - curr
                result += left_max - arr[lo];
                lo++;
            }
            else
            {
                if(arr[hi] > right_max)
                  
                // update right maximum
                right_max = arr[hi];
                  
                else
                result += right_max - arr[hi];
                hi--;
            }
        }
           
        return result;

    }
https://discuss.leetcode.com/topic/18720/8-lines-c-c-java-python-solution
    public int trap(int[] height) {
        int n = height.length, l = 0, r = n - 1, water = 0, minHeight = 0;
        while (l < r) {
            while (l < r && height[l] <= minHeight)
                water += minHeight - height[l++];
            while (r > l && height[r] <= minHeight)
                water += minHeight - height[r--];
            minHeight = Math.min(height[l], height[r]);
        }
        return water;
    }
https://discuss.leetcode.com/topic/26932/very-concise-java-solution-no-stack-with-explanations
public int trap(int[] height) {
 int secHight = 0;
 int left = 0;
 int right = height.length - 1;
 int area = 0;
 while (left < right) {
  if (height[left] < height[right]) {
   secHight = Math.max(height[left], secHight);
   area += secHight - height[left];
   left++;
  } else {
   secHight = Math.max(height[right], secHight);
   area += secHight - height[right];
   right--;
  }
 }
 return area;
}
https://discuss.leetcode.com/topic/36865/explanatory-and-concise-java-implementation
    public int trap(int[] height) {
        if(height == null || height.length == 0) return 0;
        int leftMax = 0, rightMax = 0, waterTrapped = 0, left = 0, right = height.length-1;
        while(left < right) {
            leftMax = leftMax > height[left] ? leftMax : height[left];
            rightMax = rightMax > height[right] ? rightMax : height[right];
            waterTrapped += leftMax < rightMax ? leftMax - height[left++] : rightMax - height[right--];
        }
        return waterTrapped;
    }

https://yujia.io/blog/2015/11/18/LeetCode-42-Trapping-Rain-Water/
X. Left and right array.
http://www.geeksforgeeks.org/trapping-rain-water/
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. Below is C++ implementation of this solution.
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;
}

int trap(int A[], int n) {
        if (n<2){return 0;}   
         
        int *l = new int[n];
        int *r = new int[n];
         
        int water =0;
         
        l[0]=0;
        for (int i=1;i<n;i++){
            l[i]= max(l[i-1], A[i-1]);
        }
                 
        r[n-1] = 0;
        for (int i=n-2;i>=0;i--){
            r[i]=max(r[i+1],A[i+1]);
        }
         
        for (int i=0;i<n;i++){
            if (min(l[i],r[i])-A[i] >0 ){
                water += min(l[i],r[i])-A[i];
            }
        }
        return water;
         
    }
public int trap(int[] A) {
        if (A == null || A.length == 0)
            return 0;
        int n = A.length;
        // Used to record the maximum height to the left and the right of each bar
        int[] maxHeights = new int[n];
        // Scan from left to right, find the maximum height to the left of each bar
        int maxHeight = 0;
        for (int i = 0; i < n; i++) {
            maxHeights[i] = maxHeight;
            maxHeight = Math.max(maxHeight, A[i]);
        }
        // Scan from right to left, find the maximum height to the right of each bar
        // The minimum of them is the height of the water (if any) on the bar
        // The difference between the height of the water and that of the bar is the
        // volume of the water on that bar
        maxHeight = 0;
        int volume = 0;     // Accumulated volume of water
        for (int i = n-1; i >= 0; i--) {
            maxHeights[i] = Math.min(maxHeight, maxHeights[i]);
            maxHeight = Math.max(maxHeight, A[i]);
            if (maxHeights[i] > A[i])       // Has water on the bar
                volume += maxHeights[i] - A[i];     // Accumulate the volume of the water
        }
        return volume;
    }


X. Ordered stack
https://leetcode.com/problems/trapping-rain-water/discuss/17414/A-stack-based-solution-for-reference-inspired-by-Histogram
The main idea is : if we want to find out how much water on a bar(bot), we need to find out the left larger bar's index (il), and right larger bar's index(ir), so that the water is (min(A[il],A[ir])-A[bot])*(ir-il-1), use min since only the lower boundary can hold water, and we also need to handle the edge case that there is no il.
To implement this we use a stack that store the indices with decreasing bar height, once we find a bar who's height is larger, then let the top of the stack be bot, the cur bar is ir, and the previous bar is il.
public int trap(int[] A) {
        if (A==null) return 0;
        Stack<Integer> s = new Stack<Integer>();
        int i = 0, maxWater = 0, maxBotWater = 0;
        while (i < A.length){
            if (s.isEmpty() || A[i]<=A[s.peek()]){
                s.push(i++);
            }
            else {
                int bot = s.pop();
                maxBotWater = s.isEmpty()? // empty means no il
                0:(Math.min(A[s.peek()],A[i])-A[bot])*(i-s.peek()-1);
                maxWater += maxBotWater;
            }
        }
        return maxWater;
    }
https://leetcode.com/articles/trapping-rain-water/#approach-3-using-stacks-accepted
int trap(vector<int>& height)
{
    int ans = 0, current = 0;
    stack<int> st;
    while (current < height.size()) {
        while (!st.empty() && height[current] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty())
                break;
            int distance = current - st.top() - 1;
            int bounded_height = min(height[current], height[st.top()]) - height[top];
            ans += distance * bounded_height;
        }
        st.push(current++);
    }
    return ans;
}
http://bangbingsyb.blogspot.com/2014/11/leetcode-trapping-rain-water.html
能积水的地方必然是一个中间低两边高的凹陷。所以寻找的目标是一个递减序列之后的递增。由于积水量只有在递增时才能计算，而计算又可能需要用到递减序列中的多个bar。因此必须将递减序列cache起来。这里使用stack。为了便于面积计算中宽度的计算，stack存放的不是递减序列bar的高度，而是每个bar的坐标。
    int trap(int A[], int n) {
        if(n<3) return 0;
        stack<int> s;
        s.push(0);
        int water = 0;
        
        for(int i=1; i<n; i++) {
            if(A[i]>A[s.top()]) {
                int bottom = A[s.top()];
                s.pop();
                while(!s.empty() && A[i]>=A[s.top()]) {
                    water += (A[s.top()]-bottom)*(i-s.top()-1);
                    bottom = A[s.top()];
                    s.pop();
                }
                if(!s.empty()) water += (A[i]-bottom)*(i-s.top()-1);
            }
            s.push(i);
        }
        
        return water;
    }
https://discuss.leetcode.com/topic/4939/a-stack-based-solution-for-reference-inspired-by-histogram
if we want to find out how much water on a bar(bot), we need to find out the left larger bar's index (il), and right larger bar's index(ir), so that the water is (min(A[il],A[ir])-A[bot])*(ir-il-1), use min since only the lower boundary can hold water, and we also need to handle the edge case that there is no il.
To implement this we use a stack that store the indices with decreasing bar height, once we find a bar who's height is larger, then let the top of the stack be bot, the cur bar is ir, and the previous bar is il.
https://discuss.leetcode.com/topic/29113/java-with-stack-following-the-approach-similar-to-largest-rectangle-in-histogram
Indeed this question can be solved in one pass and O(1) space, but it's probably hard to come up with in a short interview. If you have read the stack O(n) solution for Largest Rectangle in Histogram, you will find this solution is very very similar.
The main idea is : if we want to find out how much water on a bar(bot), we need to find out the left larger bar's index (il), and right larger bar's index(ir), so that the water is (min(A[il],A[ir])-A[bot])*(ir-il-1), use min since only the lower boundary can hold water, and we also need to handle the edge case that there is no il.
To implement this we use a stack that store the indices with decreasing bar height, once we find a bar who's height is larger, then let the top of the stack be bot, the cur bar is ir, and the previous bar is il.
public int trap(int[] A) {
        if (A==null) return 0;
        Stack<Integer> s = new Stack<Integer>();
        int i = 0, maxWater = 0, maxBotWater = 0;
        while (i < A.length){
            if (s.isEmpty() || A[i]<=A[s.peek()]){
                s.push(i++);
            }
            else {
                int bot = s.pop();
                maxBotWater = s.isEmpty()? // empty means no il
                0:(Math.min(A[s.peek()],A[i])-A[bot])*(i-s.peek()-1);
                maxWater += maxBotWater;
            }
        }
        return maxWater;
    }

X.
http://www.cnblogs.com/TenosDoIt/p/3812880.html算法5：可以换一种思路，如下图，如果我们求出了两个红色框的面积，然后再减去框内黑色柱子的面积，就是水的面积了，时间复杂度O(N),空间O(1), 数组扫描2次
image
如何求红色框内的面积呢，我们先求出最大的柱子高度，然后左右分开求。求面积是是一层一层的累加
image
    int trap(int A[], int n) {
        int maxHeight = 0, maxIdx = 0;
        for(int i = 0; i < n; i++)//求最大高度
            if(A[i] > maxHeight)
            {
                maxHeight = A[i];
                maxIdx = i;
            }
        int height = 0;
        int pillarArea = 0;//柱子面积
        int totalArea = 0;//总面积
        for(int i = 0; i < maxIdx; i++)
        {
            if(A[i] > height)
            {
                totalArea += (A[i] - height)*(maxIdx - i);
                height = A[i];
            }
            pillarArea += A[i];
        }
        height = 0;
        for(int i = n-1; i > maxIdx; i--)
        {
            if(A[i] > height)
            {
                totalArea += (A[i] - height)*(i - maxIdx);
                height = A[i];
            }
            pillarArea += A[i];
        }
        return totalArea - pillarArea;
    }
https://tenderleo.gitbooks.io/leetcode-solutions-/content/GoogleHard/42.html
    public int trap(int[] height) {

        int peak = 0;
        int max = 0;
        for(int i=0; i< height.length; i++){
            if(height[i] > max){
                max = height[i];
                peak = i;
            }
        }
        int amount  =0;
        int leftMax =0;
        for(int i=0; i<peak; i++){
            if(height[i] >= leftMax){
                leftMax = height[i];
            }else{
                amount += (leftMax - height[i]);
            }
        }
        int rightMax =0;
        for(int i= height.length-1; i> peak; i--){
            if(height[i] >= rightMax){
                rightMax = height[i];
            }else{
                amount += (rightMax - height[i]);
            }
        }

        return amount;
    }
算法6：参考here，也是和算法5一样求面积，但是这里利用上一题的左右指针思想，只需要扫描一遍数组
    int trap(int A[], int n) {
        int left = 0, right = n-1;
        int totalArea = 0, pillarArea = 0, height = 0;
        while(left <= right)
        {
            if(A[left] < A[right])
            {
                if(A[left] > height)
                {
                    totalArea += (A[left]-height)*(right - left + 1);
                    height = A[left];
                }
                pillarArea += A[left];
                left++;
            }
            else
            {
                if(A[right] > height)
                {
                    totalArea += (A[right]-height)*(right - left + 1);
                    height = A[right];
                }
                pillarArea += A[right];
                right--;
            }
        }
        return totalArea - pillarArea;
    }
Code from https://coderwall.com/p/outcbg
先计算柱状图的凸包面积，然后减去柱状图本身的面积，就是所能存储水的多少。时间复杂度：O(n)，空间复杂度：O(1)。
int trap(int A[], int n) { if(n<=2) return 0; int sum=A[0],mi=0; for(int i=1;i<n;i++) { sum+=A[i]; if(A[i]>A[mi]) mi=i; } int left=0,right=0,min=0;
// A[min] is the running max for(int i=1;i<=mi;i++) if(A[i]>=A[min]) { left+=A[min]*(i-min); min=i; } min=n-1; for(int j=n-2;j>=mi;j--) if(A[j]>=A[min]) { right+=A[min]*(min-j); min=j; } return left+right+A[mi]-sum; }

EPI Solution: Trapping water

trapping-rain-water.cc TrappingRainWater.java


  private static int getIndexOfMaxElement(List<Integer> A) {

    int max = Integer.MIN_VALUE;

    int maxH = -1;

    for (int i = 0; i < A.size(); i++) {

      if (A.get(i) > max) {

        max = A.get(i);

        maxH = i;

      }

    }

    return maxH;

  }

  public static int calculateTrappingWater(List<Integer> A) {

    if (A.isEmpty()) {

      return 0;

    }
    // Finds the index with maximum height.
    int maxH = getIndexOfMaxElement(A);

    // Calculates the water within [1 : maxH - 1].
    int sum = 0, left = A.get(0);
    for (int i = 1; i < maxH; ++i) {
      if (A.get(i) >= left) {
        left = A.get(i);
      } else {
        sum += left - A.get(i);
      }
    }

    // Calculates the water within [maxH + 1 : A.size() - 2].
    int right = A.get(A.size() - 1);
    for (int i = A.size() - 2; i > maxH; --i) {
      if (A.get(i) >= right) {
        right = A.get(i);
      } else {
        sum += right - A.get(i);
      }
    }
    return sum;
  }
  // Stack approach, O(n) time, O(n) space
  private static int checkAnswer(List<Integer> A) {
    LinkedList<Pair<Integer, Integer>> s = new LinkedList<>();
    int sum = 0;
    for (int i = 0; i < A.size(); ++i) {
      while (!s.isEmpty() && s.peek().getSecond() <= A.get(i)) {
        int bottom = s.pop().getSecond();
        if (s.isEmpty()) {
          break;
        }
        int top = Math.min(s.peek().getSecond(), A.get(i));
        sum += (top - bottom) * (i - s.peek().getFirst() - 1);
      }
      s.push(new Pair<>(i, A.get(i)));
    }
    return sum;
  }

Twitter waterflow problem and loeb
https://gist.github.com/mkozakov/59af0fd5bddbed1a0399
public static int calculateVolume(int[] land) {
 
    int leftMax = 0;
    int rightMax = 0;
    int left = 0;
    int right = land.length - 1;
    int volume = 0;
 
    while(left < right) {
        if(land[left] > leftMax) {
            leftMax = land[left];
        }
        if(land[right] > rightMax) {
            rightMax = land[right];
        }
        if(leftMax >= rightMax) {
            volume += rightMax - land[right];
            right--;
        } else {
            volume += leftMax - land[left];
            left++;
        }
    }
    return volume;
}
https://discuss.leetcode.com/topic/7612/java-10-lines-accepted-code-o-n-time-o-1-space-is-there-a-better-solution
Basically this solution runs two pointers from two sides to the middle, and the plank is used to record the height of the elevation within a certain range, plank height can only increase (or remain the same) from two sides to the middle. If the current pointer is pointing at a number that is less than the current plank height, the difference between plank height and the number would be the amount of water trapped. Otherwise, A[i] == plank, no water is trapped.
    public int trap(int[] A) {
        int i = 0, j = A.length - 1, result = 0, plank = 0;
        while(i <= j){
            plank = plank < Math.min(A[i], A[j]) ? Math.min(A[i], A[j]) : plank;
            result = A[i] >= A[j] ? result + (plank - A[j--]) : result + (plank - A[i++]);
        }
        return result;
    }
http://fisherlei.blogspot.com/2013/01/leetcode-trapping-rain-water.html
如果我是面试官的话，在这里可以加一个变形。不求所有容积，而是求容积中的最大值。这样就类似于Container With Most Water，但是又有不同的地方。这题里面每一个坐标本身是占体积的。所以从两边往中间扫的时候，根本不知道中间坐标共占用了多少体积。


https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/042_Trapping_Rain_Water.java
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for (int i = 0; i < height.length; i ++) {
            while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                int cur = height[stack.pop()];
                if (!stack.isEmpty())
                    ans += (i - stack.peek() - 1) * (Math.min(height[i], height[stack.peek()]) - cur);
            }
            stack.push(i);
        }
        return ans;
    }
}

// new two scan
    public int trap(int[] height) {
        int[] water = new int[height.length];
        int bar = 0, ans = 0;
        for (int i = 0; i < height.length; i ++) {
            bar = Math.max(bar, height[i]);
            water[i] = bar;
        }
        bar = 0;
        for (int i = height.length - 1; i >= 0; i --) {
            bar = Math.max(bar, height[i]);
            water[i] = Math.min(water[i], bar);
            ans += water[i] - height[i];
        }
        return ans;
    }
}

// one scan two pointer
    public int trap(int[] height) {
        int ans = 0, l = 0, r = height.length - 1;
        int barL = 0, barR = 0;
        while (l <= r) {
            barL = Math.max(barL, height[l]);
            barR = Math.max(barR, height[r]);
            if (barL < barR) ans += barL - height[l ++];
            else ans += barR - height[r --];
        }
        return ans;
    }


1. 变体(-1 表示漏漏⽔水， V存的⽔水都能漏漏下)
[3, 1, -1, 2, 1, 2] 结果为1， [2,1,2] subarray 可以存⽔水
[3, 1, 1, 2, 1, 2] 结果为3，subarray [3, 1, 1, 2] [2,1,2] 都可以存⽔水
2. 主要的变化就是每个bar有不不同的宽度
4. 变体1三种⽅方法都
⽐比较好写，清空stack或者bar变成0
5. 变体2⽅方法2/3⽐比较好写，直接乘上宽度

at
Labels: , , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts