最近在网上看到一道twitter的算法面试题，网上已经有人给出了答案，不过可能有些人没太看明白（我也未验证是否正确），现在给出一个比较好理解的答案。先看一下题目。
图1
先看看图图1。可以将方块看做砖。题干很简单，问最多能放多少水。例如，图2就是图1可放的最多水（蓝色部分），如果将一块砖看做1的话，图2就是能放10个单位的水。
图2
再看个例子
图3
图3可以放17个单位的水。
上面每一个图的砖墙用int数组表示，每一个数组元素表示每一列砖墙的砖数（高度），例如，图3用数组表示就是int[] wallheights = new int[]{2, 5, 1, 3, 1, 2, 1, 7, 7, 6};
这里某人给出了python的算法，不过有人说有问题，有python环境的可以验证。现在给出我的java算法。
算法原理
其实很简单，我的算法并不是累加的，而是用的减法，先用图3为例。只需要找到所有墙中最高的，然后再找出第二高的。如果两堵墙紧邻者，就忽略它，否则算一
下
如果墙之间没有任何其他的砖的情况下可以有多少水（只是一个乘法而已），然后扫描两堵墙之间有多少块砖，减去这个砖数就可以了。最后用递归处理。将两堵墙
两侧到各自的左右边界再重新进行前面的操作（递归处理）。直到无墙可处理。 用递归方法很容易理解。下面看一下算法的详细代码。
public class test
{
static int result = 0; // 最终结果
static int[] wallheights = new int[]
{1,6,1,2,3,4,100,1,9}; // 表示所有的墙的高度
public static void process(int start, int end)
{
// first：start和end之间最高的墙
// second：start和end之间第二高的墙
int first = 0, second = 0;
// firstindex：第一高的墙在wallheights中的索引
// secondindex：第二高的墙在wallheights中的索引
int firstindex = 0, secondindex = 0;
// 两堵墙必须至少有一堵墙的距离
if (end - start <= 1)
return;
// 开始获取第一高和第二高墙的砖数
for (int i = start; i <= end; i )
{
if (wallheights[i] > first)
{
second = first;
secondindex = firstindex;
first = wallheights[i];
firstindex = i;
}
else if (wallheights[i] > second)
{
second = wallheights[i];
secondindex = i;
}
}
// 获取左侧墙的索引
int startindex = math.min(firstindex, secondindex);
// 获取右侧墙的索引
int endindex = math.max(firstindex, secondindex);
// 计算距离
int distance = endindex - startindex;
// 如果第一高的墙和第二高的墙之间至少有一堵墙，那么开始计算这两堵墙之间可以放多少个单位的水
if (distance > 1)
{
result = result (distance - 1) * second;
// 减去这两堵墙之间的砖数
for (int i = startindex 1; i < endindex; i )
{
result -= wallheights[i];
}
}
// 开始递归处理左侧墙距离开始位置能放多少水
process(start, startindex);
// 开始递归处理右侧墙距离结束位置能放多少水
process(endindex, end);
}
public static void main(string[] args)
{
process(0, wallheights.length - 1);
system.out.println(result);
}
}
代码中的测试用例的结果是22。下面是几组测试用例。
[2,5,1,2,3,4,7,7,6] 结果：10
[2,5,1,3,1,2,1,7,7,6] 结果：17
[6,1,4,6,7,5,1,6,4] 结果：13
[9,6,1,2,3,4,50,1,9] 结果：37
有其他算法的（语言不限）欢迎跟帖
《android开发完全讲义（第2版）》（本书凯发k8网页登录的版权已输出到台湾）
《android高薪之路：android程序员面试宝典 》
新浪微博： 昵称：李宁_lining