Leetcode算法Java全解答--42.接雨水.md

Posted by lizhao on 07-09,2019

Leetcode算法Java全解答--42.接雨水

[toc]

题目

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

示例:

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


## 想法


## 结果

// TODO

## 总结

// TODO

## 代码
### 我的答案

public class Solution { public int trap(int[] height) { int length; int maxLeftHeight = 0, maxRightHeight = 0; int result = 0; int temp;

    if (height == null || (length = height.length) == 0)
        return 0;
    int[] leftMaxHeight = new int[length];
    int[] rightMaxHeight = new int[length];

    for (int i = 0; i < length; i++) {
        leftMaxHeight[i] = maxLeftHeight;
        maxLeftHeight = Math.max(maxLeftHeight, height[i]);
    }

    for (int i = length - 1; i >= 0; i--) {
        rightMaxHeight[i] = maxRightHeight;
        maxRightHeight = Math.max(maxRightHeight, height[i]);
    }

    for (int i = 0; i < length; i++) {
        temp = Math.min(leftMaxHeight[i], rightMaxHeight[i]);
        if (temp >= height[i])
            result += temp - height[i];
    }

    return result;
}

}


### 大佬们的答案


### 测试用例


## 其他
代码托管码云地址:[https://gitee.com/lizhaoandroid/LeetCodeAll.git](https://gitee.com/lizhaoandroid/LeetCodeAll.git)

查看其他内容可以点击专栏或者我的博客哈:[https://blog.csdn.net/cmqwan](https://blog.csdn.net/cmqwan)

“大佬们的答案” 标签来自leetcode,侵权请联系我进行删改

如有疑问请联系,联系方式:QQ3060507060