# 11.Container With Most Water <span class="tag" data-diff="medium" />
{%hackmd RN5D4nggQRO8wzNqxuvlNw %}

## 題目
Given n non-negative integers $a_1, a_2, ..., a_n$ , 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, a_i)$ and $(i, 0)$. Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
**Example:**

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

## 思路
最簡單的做法是跑2個迴圈，將所有結果找出最大值。但這樣的做法需要 $O(n^2)$ 的時間複雜度。於是我自己想出來另一個做法，主要概念是水從最低的柱子往上淹，該柱子會去找離他最遠還沒被淹掉的的另一根柱子，計算之間的面積，更新最大值，另外會maintain一個array，紀錄還沒被淹掉的柱子。

let x = height.map((x,i) => i),
    y = height.map((x, i) => [i, x]).sort((a,b) => b[1] - a[1]);

let temp,
    max = 0;

while(temp = y.pop()){
    let [a, b] = temp;
    x.splice(x.indexOf(a), 1);

    let d_x = Math.max(a - x[0], x[x.length - 1] - a),
        area = d_x * b;

    max = area > max ? area : max;
}
return max;

一開始會把每個元素記錄其index和高度，並以高度排序。排序會需要 $O(nlogn)$ 的時間，但之後只需要一個一個pop出元素，花費 $O(n
)$ 的時間即可找出最大值，總時間複雜度是 $O(nlogn)$。

另外，在討論區看到大神的厲害想法，也把它紀錄下來:
越大的面積需要兩個元素在x方向距離越遠，高度差越小且越接近最大高度，所以一開始最遠的兩端，計算面積，之後將較小的那一端去除，重複上述動作，計算完整個array即可得到最大值。

let max = 0, i = 0, j = height.length - 1;
while(i < j){
    max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
    if(height[j] > height[i]) i ++ ;
    else j --;
}
return max;

這種作法只需要loop過一遍array花 $O(n)$ 的時間就可以完成，真的很厲害XDD