[LeetCode][Java] Trapping Rain Water

题意：

Givennnon-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], return6.

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.Thanks Marcosfor contributing this image!

题目：

给定n个非负整数来代表高度图，每个栏的宽度为1.计算下雨之后这个东东能最多能盛多少的水。

比如，给定[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个单位。

算法分析：

当刷到这个题的时候我真是醉了。这就是15年春季的阿里算法工程师实习在线笔试的题目~~

一模一样，当时水笔的我真心不会做啊，笔试果断没过 囧~~

* 观察下就可以发现被水填满后的形状是先升后降的塔形，因此，先遍历一遍找到塔顶，然后分别从两边开始，，往塔顶所在位置遍历，水位只会增高不会减小，

* 且一直和最近遇到的最大高度持平，这样知道了实时水位，就可以边遍历边计算面积。

* 首先找到最高的，然后从左往最高处扫，

* 碰到一个数A[i]，计算A[0,,,i-1]最高的是否高过A[i]，

* 如果是，则A[i]上的水的体积为max(A[0…i-1])-A[i],否则为0并且更新最大值

AC代码：

public class Solution { public int trap(int[] height){if(height==null||height.length==0)return 0;int res=0;int maxvalue=0;int label=0;int startmvalue=0;int endmvalue=0;int mtem;for(int i=0;i<height.length;i++){if(height[i]>maxvalue){maxvalue=height[i];label=i;}}startmvalue=height[0];for(int i=0;i<label;i++){if(height[i]>startmvalue) startmvalue=height[i];else{res+=startmvalue-height[i];}}endmvalue=height[height.length-1];for(int i=height.length-1;i>label;i–){if(height[i]>endmvalue) endmvalue=height[i];else{res+=endmvalue-height[i];}}return res;}}

版权声明：本文为博主原创文章，转载注明出处

十年干戈天地老，四海苍生痛苦深。