Leetcode 42题 接雨水（Trapping Rain Water）

题目链接

https://leetcode-cn.com/problems/trapping-rain-water/

题目内容

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例图

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

思路

我们可以设置两个数组，「left_height_array」和「right_height_array」; 其中「left_height_array」表示当前柱子前面的所有柱子的最高值（不包括当前柱子）； 「right_height_array」表示当前柱子后面的所有柱子的最高值（不包括当前柱子）； 取left_height_array[i]与right_height_array[i]两个值的最小值，如果相等则取这个相同的值，存储在「res」数组中 在height[i]处可以存的水量的求法： 如果res[i]的值比height[i]大，当前凹处可以存res[i] - height[i]的水; 如果res[i]的值不比height[i]大，不能存水； 再把res[i]累加便可以得到最终存水量。 （其实可以在比较「left_height_array[i]」 与 「right_height_array[i]」 大小关系时就可以进行累加存水量了。）

案例分析

「height」 : [0,1,0,2,1,0,1,3,2,1,2,1] 先求解**left_height_array[i]**从前往后算： 第一个元素左边没有元素，所以left_height_array[0] = 0； 第二个元素左边元素有0，左边最高的是0，所以left_height_array[1] = 0; 第三个元素左边元素有0，1，左边最高的是1，所以left_height_array[2] = 1; 第四个元素左边元素有0，1，0，左边最高的是1，所以left_height_array[3] = 1; 第五个元素左边元素有0，1，0，2，左边最高的是2，所以left_height_array[4] = 2; 第六个元素左边元素有0，1，0，2，1左边最高的是2，所以left_height_array[5] = 2; 第七个元素左边元素有0，1，0，2，1，0，左边最高的是2，所以left_height_array[6] = 2; 第八个元素左边元素有0，1，0，2，1，0，1左边最高的是2，所以left_height_array[7] = 2; 第九个元素左边元素有0，1，0，2，1，0，1，3左边最高的是3，所以left_height_array[8] = 3; 第十个元素左边元素有0，1，0，2，1，0，1，3，2左边最高的是3，所以left_height_array[9] = 3; 第十一个元素左边元素有0，1，0，2，1，0，1，3，2，1左边最高的是3，所以left_height_array[10] = 3; 第十二个元素左边元素有0，1，0，2，1，0，1，3，2，1，2左边最高的是3，所以left_height_array[11] = 3;

所以left_height_array数组为 0，0，1，1，2，2，2，2，3，3，3，3 同理可求得right_height_array数组为 3，3，3，3，3，3，3，2，2，2，1，0； height数组为： 0，1，0，2，1，0，1，3，2，1，2，1 index=0时，left_height_array[0] = 0,right_height_array[0] = 0不能放水，存水量为0； index=1时，left_height_array[1] = 0,right_height_array[1] = 3不能放水，两者最小为0，存水量为0； index=2时，left_height_array[2] = 1,right_height_array[1] = 3不能放水，两者最小为2，而height[i]为0，存水量为两者最小值 - height[i] = 1； 以此类推； 最后把它们都相加即可。

代码

class Solution {
    public int trap(int[] height) {
        int result = 0;
        if(height.length == 0) return result;
        int[] left_height_array = new int[height.length];
        int[] right_height_array = new int[height.length];
        int left_max = 0;
        int right_max = 0;
        left_height_array[0] = 0;
        right_height_array[0] = 0;
        for(int i = 1;i<height.length;i++){
            if(height[i-1]>left_max){
                left_max = height[i-1];
            }
            left_height_array[i] = left_max;
        }

        for(int i = height.length -2;i>=0;i--){
            if(height[i+1]>right_max){
                right_max = height[i+1];
            }
            right_height_array[i] = right_max;
        }
        for(int i=0;i<height.length;i++){
            if(left_height_array[i] == right_height_array[i]){
                if(left_height_array[i] > height[i])
                    result+=left_height_array[i]-height[i];

            }else if(left_height_array[i] < right_height_array[i]){
                if(left_height_array[i] > height[i])
                    result+=left_height_array[i]-height[i];
            }else{
                if(right_height_array[i]>height[i])
                    result += right_height_array[i] - height[i];
            }
        }
        return result;
    }
}