Twitter算法面试题详解（Java实现） - 银河使者 - 博客园

Twitter算法面试题详解（Java实现） - 银河使者 - 博客园

Twitter算法面试题详解（Java实现）

     最近在网上看到一道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为例。只需要找到所有墙中最高的，然后再找出第二高的。如果两堵墙紧邻者，就忽略它，否则算一下 如果墙之间没有任何其他的砖的情况下可以有多少水（只是一个乘法而已），然后扫描两堵墙之间有多少块砖，减去这个砖数就可以了。最后用递归处理。将两堵墙 两侧到各自的左右边界再重新进行前面的操作（递归处理）。直到无墙可处理。 用递归方法很容易理解。下面看一下算法的详细代码。

Read full article from Twitter算法面试题详解（Java实现） - 银河使者 - 博客园