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. 

 

Solution 1:

分析某个柱子，发现该柱子上水的高度和其左右两边的最高柱子有关，设该柱子左边所有柱子中最高的为leftmax，右边所有柱子中最高的为rightmax，如果min(leftmax, rightmax) 大于该柱子的高度，那么该柱子上可以蓄水为min(leftmax, rightmax) - 该柱子高度，如果min(leftmax, rightmax) <= 该柱子高度，则该柱子上没有蓄水。

可以从后往前扫描一遍数组求得某个柱子右边的最高柱子，从前往后扫描一遍数组求得某个柱子左边的最高柱子, 然后按照上面的分析可以求得所有的蓄水量。

public int trap(int[] A) {
    int n = A.length, waterSum = 0;
    int[] rightMax = new int[n];
    int maxH = 0;
    for(int i=n-1; i>=0; i--) {
        rightMax[i] = maxH;
        maxH = Math.max(maxH, A[i]);
    }
    maxH = 0;
    for(int i=0; i<n; i++) {
        int minH = Math.min(maxH, rightMax[i]);
        if(A[i] < minH) {
            waterSum += minH - A[i];
        }
        maxH = Math.max(maxH, A[i]);
    }
    return waterSum;
}

 

Solution 2:

Keep track of the already safe level and the total water so far. In each step, process and discard the lower one of the leftmost or rightmost elevation.

这个方法是最优解，只用了Constant O(1) 的Memory。

int trap(vector<int>& height) {
    int l = 0, r = height.size()-1, level = 0, water = 0;
    while (l < r) {
        int lower = height[height[l] < height[r] ? l++ : r--];
        level = max(level, lower);
        water += level - lower;
    }
    return water;
}

 

Reference:

https://leetcode.com/discuss/45812/7-lines-c-c