最近在網上看到一道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
有其他算法的（語言不限）歡迎跟帖
新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining