[LeetCode] 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.

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!

Subscribe to see which companies asked this question

1. Can be solved with two pointers, details is kind of tricky, when minus pole heights, subtract previous overlapping, etc. 

public class Solution {
 public class Solution {
    public int trap(int[] height) {
        int len = height.length;
        
        if(0 == len)
            return 0;
        
        int res = 0;
            
        int l = 0;
        int r = len -1;
        
        while(l < r){
            int p = Math.min(height[l], height[r]);
            res += p * (r - l);
            if(height[l] < height[r]){
                // Error: <= p, but not sm than p, not only wrong answer, but dead loop. 
                while(l < r && height[l] < = p){
                    res -= height[l];
                    ++l;
                }
            }
            else{
                while(l < r && height[r] < = p){
                    res -= height[r];
                    --r;
                }
            }
            if(l < r){
                res -= p * (r - l);
            }
        }
        
        /*
        Error: subtraction the height of pole is not correct. [0, 2, 0]
        for(int i = 0; i < len; ++i){
            res -= height[i];
        }
        */
        
        return res;
    }
}