[LeetCode][Java] Trapping Rain Water

宝剑锋从磨砺出，梅花香自苦寒来。这篇文章主要讲述[LeetCode][Java] Trapping Rain Water相关的知识，希望能为你提供帮助。
题意：
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. Thanks Marcos for 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年春季的阿里算法project师实习在线笔试的题目~~
一模一样，当时水笔的我真心不会做啊，笔试果断没过囧~~
* 观察下就能够发现被水填满后的形状是先升后降的塔形。因此。先遍历一遍找到塔顶，然后分别从两边開始，往塔顶所在位置遍历，水位仅仅会增高不会减小，
* 且一直和近期遇到的最大高度持平，这样知道了实时水位。就能够边遍历边计算面积。
* 首先找到最高的，然后从左往最高处扫。
* 碰到一个数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=https://www.songbingjia.com/android/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; } }

【[LeetCode][Java] Trapping Rain Water】