Trapping Water

Question quoted from lintcode

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.

pic

Example
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Idea

This question seems easy but indeed tough. You can manually do it intuitively but hardly in code. This is because with a human eye you can easily see the higher bars from left to right until the end. And you will do it by filling water from left, and you will make sure the water level does not exceed the leftmost-high bar and rightmost-high bar.

But why do you know which bar is the leftmost-high and which bar is the rightmost-high given a segment? I spent pretty much time trying to understand how my brain works.

Eventually, I didn't figure it out. But I found a way to let the computer do this.

Steps

• stepping from left, mark the largest height that is ever seen before this element
• stepping from right, mark the largest height that is ever seen before this element
• The water level is the minimum amongst the left boundary bar and right boundary bar. If the element height does not exceed the water level, then we can fill the water.

步驟

• 從左到右掃描一遍，記錄下當下元素之前遇到的最高值。此爲當下元素的左邊界
• 從右到左掃描一遍，記錄下當下元素之前遇到的最高值。此爲當下元素的右邊界。
• 從頭到尾掃描一遍，水平面是當下元素之左右邊界的較小值。若水平面比當下元素高，則可以加水。

Solution

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] heights) {
        if (heights.length == 0) return 0;
        
        
        int[] leftMax = new int[heights.length];
        leftMax[0] = 0;
        for(int i = 1; i < heights.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], heights[i - 1]);
        }
        
        int[] rightMax = new int[heights.length];
        rightMax[heights.length - 1] = 0;
        for(int i = heights.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], heights[i + 1]);
        }

        int water = 0;
        for(int i = heights.length - 1; i >= 0; i--) {
            int waterLevel = Math.min(leftMax[i], rightMax[i]);
            if (waterLevel > heights[i]) {
                water += waterLevel - heights[i];
            }
        }
        return water;
    }
    
}