问题描述：在下图里我们有不同高度的挡板。这个图片由一个整数数组所代表，数组中每个数是墙的高度。下图可以表示为数组（2、5、1、2、3、4、7、2）。假如开始下雨了，那么挡板之间的水坑能够装多少水（水足够多）呢？
下图是装满水的情况，一个蓝色格子代表一个单位的水。下图中一共装了10个单位的水。
问题分析：
先看看下图，判断哪个单元格的水能留下来。下图中的两个单元格，一个红色的单元格和一个绿色的单元格，哪个单元格的水是溜走了，哪个单元格的水能留下来？
很明显的，上图中的红色单元格的水会流走，绿色单元格的水会被留下来。
那么，仔细看看这两个单元格的区别在哪儿
区别就是，红色单元格只有右边的挡板比它高（不低于它），而绿色单元格左右两边都有挡板比它高（左边最高是5，右边最高是7）
这也就很好的理解了，如果水要能留下来，必须左右两边的挡板都比它高才行。（很明显的，不管哪一侧的挡板比水低，水就会朝哪个方向流出去）
于是，我给每个挡板定义了3个属性
V属性：本挡板的高度
L属性：本挡板左侧挡板的最高高度
R属性：本挡板右侧挡板的最高高度
那么，该挡板上方能积水的充要条件就是：L＞V并且R＞V
如果该挡板能积水，则积水量为：Min（L-V，R-V）
那么总的积水量就是所有挡板的积水量总和
问题就变成，如何求出每块挡板的L属性和R属性
用V、L、R三个数组标示挡板组的三个属性。一共有N块挡板，数组的下标从0到N-1。
V（i）表示第i块挡板的高度、L（i）表示第i块挡板的L属性、R（i）表示第i块挡板的R属性
可知的是L（0）=0，R（N-1）=0；
不失一般性，考虑第i块挡板的L属性（i＞0）。L（i-1）表示第i-1块挡板的L属性。那么，可知
如果L（i-1）＞V（i-1），则L（i）=L（i-1）
如果L（i-1）≤V（i-1），则L（i）=V（i-1）
综上所述：L（i）=Max（L（i-1），V（i-1））（i＞0）
同理可述：R（i）=Max（R（i+1），V（i+1））（i<N-1）
而由于L（0）=0，R（N-1）=0。则说明第0、N块挡板（最左和最右的挡板）是不会积水的
因此，计算L和R的属性以及计算积水量的下标从1开始到N-2即可
代码如下：
Public Class clsFillWater
Public Shared Function FillWater2(ByVal ParamArray Nums() As Integer) As Integer
Dim L(Nums.Length - 1) As Integer
Dim R(Nums.Length - 1) As Integer
Dim I As Integer
Dim Result As Integer = 0
If Nums.Length < 3 Then Return 0
L(0) = 0
R(Nums.Length - 1) = 0
For I = 1 To Nums.Length - 2
L(I) = Math.Max(L(I - 1), Nums(I - 1))
R(Nums.Length - 1 - I) = Math.Max(R(Nums.Length - I), Nums(Nums.Length - I))
Next
For I = 1 To Nums.Length - 2
If L(I) > Nums(I) AndAlso R(I) > Nums(I) Then
Result += Math.Min(L(I), R(I)) - Nums(I)
End If
Next
Return Result
End Function
End Class
从代码看，该算法的时间效率是O（N）的，是线性时间的。在文章 Twitter算法面试题详解（Java实现） 的评论中也有一个线性时间的算法（效率相当，可能还优于本算法），不过理解上不如这个简单明了。
本文转自万仓一黍博客园博客，原文链接：http://www.cnblogs.com/grenet/p/3413809.html，如需转载请自行联系原作者
