# LeetCode-Container With Most Water

#### 問題

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.
Note: You may not slant the container and n is at least 2.

#### 解法

`# javapublic class Solution {    public int maxArea(int[] height) {        int maxarea = 0;        for (int i = 0; i < height.length; i++)            for (int j = i + 1; j < height.length; j++)                maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));        return maxarea;    }}`

`# rubydef max_area(height)    max_area = 0    left = 0    right = height.length - 1    while left < right        h = height[left] > height[right] ? height[right] : height[left]        w = right - left        area = h * w        max_area = area if area > max_area        if height[left] > height[right]            right = right - 1        else            left = left + 1        end    end    return max_areaend`

#### 想法

Two Pointer Approach先簡稱TPA好了，TPA的解法步驟為

1. 初始化最大面積(max_area)以及右邊(right)、左邊(left)的線，left為0，right則為陣列長度-1
2. 由於容器是以裝水為前提，所以高度為較短的線，長度則為 `right — left` ，算出面積，若面積大於max_area，則取代max_area
3. 比較兩條線的高度，若左邊較小，則左邊的線往右移 `left + 1`，反之則右邊的線往左移 `right — 1`
4. 回步驟二，直到兩條線交錯

``  1 2 3 4 5 61 x - - - - o2 x x3 x x x 4 x x x x5 x x x x x6 x x x x x x``

``  1 2 3 4 5 61 x - - - - o2 x x       o3 x x x     |4 x x x x   |5 x x x x x |6 x x x x x x``

``  1 2 3 4 5 61 x ------- o2 x x - o o o3 x x x o | |4 x x x x | |5 x x x x x |6 x x x x x x``

#### 參考

https://leetcode.com/problems/container-with-most-water/discuss/6099/yet-another-way-to-see-what-happens-in-the-on-algorithm