LeetCode #42 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!

 

分析:

给定一个数组,每个数代表该位置上的长条的高度,由此得到一个类似地形图的东西。凹进去的地方可以蓄水,问一共能存多少水。

每一个坑(凹进去的地方)都是由左右2个长条围成的。能存多少水取决于这2个长条中最短的那个。因此,我们对数组进行2次遍历。第1次从左向右,获得该位置左侧最高长条的高度;第2次从右向左,获得该位置右侧最高长条的高度。现在每个位置都知道了它所在的坑被围成的左右2个长条的高度,取较短的那个,就是该位置蓄水的最大高度。最后把每个位置的蓄水量加起来即可。

 

代码:

Java