# 11 - Container With Most Water

解法一 - 暴力法

暴力法就不贅述了，可以看我 這邊記錄 的。

解法二 - Two Pointer

在想出演算法之前，我們需要先學習觀察一些問題的特性：

1. 以直覺來說，一開始取的 container 是最外側的兩個柱子（分別用 l, r 兩個 pointer 去指），如果要把取的柱子往內移，那 height 必須比原本取的那根柱子高，因為 width 變小了

   

   以上圖來說，原本 height[l] == 1，height[r] == 7；如果要把 height[l] 往右移，width 就會減少 1，所以會希望 height[l] 變比較高，才有移動的價值。

不過接下來就有一個問題，我們要怎麼決定要內縮 l 還是 r 呢？

最直覺的想法 (Greedy 思維) 就是移動 height 比較小的那邊。因為移動 height 比較小的那邊才會讓面積增加，如果移動 height 比較大的那邊，面積只會註定變小。

所以，如果 height[l] < height[r]，就把 l 往右移。反之如果 height[r] < height[l]，就把 r 往左移。而如果 height[l] == height[r]，就把兩者都往內移。直到兩者相鄰為止。

實做出來的程式碼如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = INT_MIN, l=0, r=height.size()-1;

        while(l<r) {
            res = max(res, min(height[l], height[r])*(r-l));

            if(height[l] < height[r])
                l++;
            else if(height[l] > height[r])
                r--;
            else{ 
                l++; r--;
            }
        }

        return res;
    }
};

效率頗高！

Runtime: 16 ms, faster than 95.70% of C++ online submissions for Container With Most Water. Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Container With Most Water.