問題描述：
給定n個非負的整數(shù) a1, a2, ..., an , 其中每一個代表坐標系 (i, ai)中的一個點. 畫出n條豎線，每條線的起點和終點分別為 (i, ai) 和 (i, 0). 找到其中的兩條線谣沸，它們和x軸一起組成一個容器使得該容器裝水最多粥鞋。
PS: 容器不會傾斜经伙，并且n最小是2。
上圖中的豎線由數(shù)組 [1,8,6,2,5,4,8,3,7]給出。 在這個實例中胳徽，最大蓄水量容器 (藍色區(qū)域)可蓄水容量是49 .png
示例：
輸入： [1,8,6,2,5,4,8,3,7]
輸出： 49
一般解法
最容易想到的便是暴力法，針對每條豎線計算其和其前方所有豎線組成的容器蓄水量爽彤，最終得到這些豎線組成的所有容器中的最大值养盗。
時間復雜度：
計算次數(shù)為=
，從而時間復雜度為
适篙。
代碼實現(xiàn)
private static int solutionV1(int[] height) {
if (height == null || height.length <= 1) {
return 0;
}
int maxArea = Integer.MIN_VALUE;
int curArea;
for (int i = 1; i < height.length; i++) {
for (int j = i - 1; j >= 0; j--) {
curArea = Math.min(height[i], height[j]) * (i - j);
if (maxArea < curArea) {
maxArea = curArea;
}
}
}
return maxArea;
}
進階解法
一般解法的時間復雜度為往核，如果要優(yōu)化的話，我們需要找到更低階的解法嚷节，比如
聂儒。
通過觀察可以發(fā)現(xiàn)，對于任意的衩婚，如果
，那么有:
所以對任意的k效斑，非春，也就是說在所有包含i的容器中最大的就是
。
令缓屠，那么
奇昙。
同理，如果敌完，那么就有：
令储耐，那么
。
從上述的推理我們可以看出蠢挡，如果弧岳，我們便可以直接把i右移凳忙，否則把j左移，從而去掉一些不必要的計算禽炬，這樣便可以在
時間內(nèi)得到結(jié)果涧卵。
代碼實現(xiàn)
private static int solutionV2(int[] height) {
if (height == null || height.length <= 1) {
return 0;
}
int maxArea = 0;
int curArea;
int s = 0, e = height.length - 1;
while (s < e) {
curArea = height[s] < height[e] ? (e - s) * height[s] : (e - s) * height[e];
maxArea = maxArea > curArea ? maxArea : curArea;
if (height[s] < height[e]) {
s++;
} else {
e--;
}
}
return maxArea;
}
總結(jié)
該題是典型的需要通過數(shù)學推理才能找到更優(yōu)解法的題型，十分有趣腹尖，特此整理紀念柳恐。
