題目
原題鏈接
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
思路
首先請(qǐng)畫(huà)一個(gè)坐標(biāo)系靶累，橫坐標(biāo)x童擎，分別為0，1芯咧，2咬最，3目锭，4...(即題中所說(shuō)的 i )湃鹊，而其對(duì)應(yīng)的j為（a1, a2, ..., an）夺颤。試想在(i, ai) 和 (i, 0)兩點(diǎn)之間做線，
圖中紅色為隨意取的aj值枪汪，紅色線段就像兩個(gè)隔板涌穆，與x軸合成了一個(gè)容器用來(lái)裝水，圖中左側(cè)線段明顯比最右側(cè)線段短上一截雀久，因此我們只能取較短的一截作為容器的高度宿稀，乘上兩條線段之間距離，即min(aj,ai) *（j-i）岸啡。
代碼是從給定的兩端開(kāi)始遍歷原叮，獲得此時(shí)的容量值作為最大值；接著考慮是最左側(cè)隔板向右移動(dòng)一位呢還是最右側(cè)隔板向左移一位巡蘸，這取決于兩個(gè)隔板的高度奋隶，顯然我們希望隔板越高越好，這樣容器能夠容納的水也越多悦荒。因此如果左側(cè)隔板低于最右側(cè)唯欣，那么我們淘汰最左側(cè)的隔板，選擇left++;反之亦然搬味。
這里給出個(gè)極端的示意圖境氢，有助于理解：
顯然2比1的面積大的多蟀拷。 圖比較丑 見(jiàn)諒！
代碼
附上swift 版本：
class Solution {
func maxArea(height: [Int]) -> Int {
// 容量
var volume = 0
// 記錄數(shù)組左邊索引和右邊索引
var left = 0 , right = height.count - 1
while(left < right){
// 計(jì)算一次容量
let water = min(height[left], height[right]) * (right - left)
// 比較 獲得最大值
volume = (water > volume) ? (water) : (volume)
if( height[left] < height[right] ){
left++;
}else{
right--;
}
}
return volume
}
}
