LeetCode100之接雨水(42)--Java

1.问题描述

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

        示例1

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

        示例2 

输入：height = [4,2,0,3,2,5]
输出：9

        提示

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

        难度等级

             困难

        题目链接

               接雨水

2.解题思路

        这道接雨水的题目看着似乎很难，但是真正明白怎么做之后，就会觉得十分简单，话不多说，我们一起来看一下吧。

        每一个位置能接到多少雨水，取决于它这个位置本身的高度和它左右两边最大的高度，左右两边最大高度之中的最小值 减掉它本身的高度就是它这个位置能接到的雨水。为什么是左右两边最大高度的最小值呢？因为雨水上涨到左右两边的最大高等的其中一个时，就没有容器壁挡住它了，再接就会漏出来，最先到达的那个高度就是左右两边最大高度中的较小的那个。

        我们已经知道了每个位置能接多少水的关键，那么解决问题就是要找到这几个关键。本身的高度题目已经给我们了，所以我们只需要计算出每一个位置左右两边的最大高度即可。

        所以我们可以定义两个数组，分别存储左右两边的最大高度，然后通过for循环遍历的方式，获得每个位置左右两边的最大高度。

    //存储左边最大的高度
    int[] lMaxHeight = new int[height.length];
    //存储右边最大的高度
    int[] rMaxHeight = new int[height.length];
    //初始化数组
    lMaxHeight[0] = height[0];
    //计算每个位置左边最大的高度
    for(int i = 1;i < height.length;i++){
        lMaxHeight[i] = Math.max(lMaxHeight[i-1],height[i]);
    }
    //初始化数组
    rMaxHeight[height.length-1] = height[height.length-1];
    //计算每个位置右边最大的高度
    for(int i = height.length - 2;i >= 0;i--){
        rMaxHeight[i] = Math.max(rMaxHeight[i+1],height[i]);
    }

        三个要素都集齐之后，我们只要在每个位置取出左右最大高度的最小值再减去本身的高度，就是这个位置能够接的雨水。值得注意的是，若计算出来的雨水为负数，那其实是本身的高度大于左右两边，是无法接雨水的，所以这部分负数的值我们要舍去。将正数的雨水值累加在一起就是我们想要的答案了。

    int sum = 0;
    //计算能接多少雨水
    for(int i = 1;i < height.length-1;i++){
        //左右两边的最大高度取最小
        int count = Math.min(lMaxHeight[i],rMaxHeight[i]) - height[i];
        if(count > 0){
           sum += count;
        }
    }

3.代码展示

class Solution {
    public int trap(int[] height) {
    //存储左边最大的高度
    int[] lMaxHeight = new int[height.length];
    //存储右边最大的高度
    int[] rMaxHeight = new int[height.length];
    //初始化数组
    lMaxHeight[0] = height[0];
    //计算每个位置左边最大的高度
    for(int i = 1;i < height.length;i++){
        lMaxHeight[i] = Math.max(lMaxHeight[i-1],height[i]);
    }
    //初始化数组
    rMaxHeight[height.length-1] = height[height.length-1];
    //计算每个位置右边最大的高度
    for(int i = height.length - 2;i >= 0;i--){
        rMaxHeight[i] = Math.max(rMaxHeight[i+1],height[i]);
    }
    int sum = 0;
    //计算能接多少雨水
    for(int i = 1;i < height.length-1;i++){
        //左右两边的最大高度取最小
        int count = Math.min(lMaxHeight[i],rMaxHeight[i]) - height[i];
        if(count > 0){
           sum += count;
        }
    }
    return sum;
    }
}

4.总结

        这道题的关键就在于能不能看出它是怎么接雨水的，左右两边最大高度的最小值 - 本身的高度，为正数的那部分就是我们要的雨水。虽然这是一道困难题，但是知道怎么写后，就像我说的，十分简单。就啰嗦到这了，祝大家刷题愉快~