42. Trapping Rain Water.md

42. Trapping Rain Water

Problem

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.

tag:

• two pointers

Solution

思路很简单，逐个分析每个槽能trap water的容量，然后进行累加即为总容量。关键在于算法的优化。

每个槽的容量为其左边最高与右边最高中较低的一个与该槽高度的差值。

常规的做法是进行遍历，对每个槽的容量计算，时间复杂度为O(N²).

优化： 从左到右遍历纪录每个槽左边的最大值，从右到左遍历纪录每个槽最右边的最大值，时间复杂度O(2N）

java

    public int trap(int[] height) {
        int[] mostHeight = new int[height.length];
        int max = 0, sum = 0;
        for(int i=0; i<height.length; i++) {
            mostHeight[i] = max;
            if(max<height[i]) max = height[i];
        }
        max=0;
        for(int i=height.length-1; i>=0; i--) {
            mostHeight[i] = Math.min(max, mostHeight[i]);
            if(max<height[i]) max = height[i];
            sum += (mostHeight[i]-height[i])>0 ? (mostHeight[i]-height[i]) :0 ;
        }
        return sum;
    }

go