[LeetCode] 42. Trapping Rain Wat

</br>

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.

</br>

Solution

This problem is kind of same as Histogram.
We first could determine the start point of the process of filling water. By implementing

while(l<r && height[l]<=height[l+1])  l++;
while(l<r && height[r]<=height[r-1])  r--;

we can move the pointer to the first bar where its volume is higher than its right one, otherwise the left side cannot keep the water from escaping. The same situation goes with the right side, then can save some overall time by avoiding unnecessary time to search from those impossible spot.

Then, from the start point, whenever there is a column lower than the left barricade, we can fill the water to level the gap; and if the left barricade is lower than the current column, it means this loop should be terminated and to find a new left barricade. The same situation goes with the right side.

Finally, dealing with the null situation by return 0 when the length of the array is shorter than 3, we should be good to go.

The code is shown as below.
Java

public class Solution {
    public int trap(int[] height) {
        
        if(height.length<3) return 0;
            
        int area = 0, l = 0, r = height.length-1;
        
        //Find the start pointer to avoid unnecessary calculation 
        while(l<r && height[l]<=height[l+1])  l++;
        while(l<r && height[r]<=height[r-1])  r--;
        
        while(l<r){
            int left = height[l], right = height[r];
            if (left <= right) {
            while (l < r && left >= height[++l]) 
                area += left - height[l];
            } else {
                while (l < r && height[--r] <= right) 
                    area += right - height[r];
            }
        }
        
        return area;
    }
}

</br>