leetcode-11 Container With Most Water

題意: 給定一個數組,假設值代表板子高度,index代表板子位子,求任選兩塊板子裝水(p.s兩塊版子中間的其他版子此時視為不存在),所能裝的最多水量


解題思路: 利用雙指針,其中一指針指向數組開頭,另一指針指向數組尾端,記錄此時面積,和原先記錄的答案比較;之後,將指向比較矮木板的指針往另外一塊木板方向移動,複雜度為O(n),其中n為數組元素個數


演算法實現不難,難的是理解為何演算法是正確的,我們可以來簡單證明一下,如果這種移動木塊的方法能夠涵蓋所有情況,則這個演算法會是正確的,我們可以想一下為何移動的是矮木板,因為如果移動的是指向高木板的指針,則所圍成的面積必定下降,因為不管下一塊被指向的木板的高度比較高或一樣,則新的面積為矮木板高度乘與較短的寬度;或較矮,則新的面積為新木板乘與較少寬度,所以矮木板移動時,即表示之前矮木板所能形成的最大面積已經被考慮了!!每次移動木板即表示被移動木板的所有情況已經被考慮,因為一開始從兩端開始移動,又最終兩塊木板重合,即表示所有情形皆被考慮,故此算法成立


C++ code 如下:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l=0;
        int r=height.size()-1;
        int ans=min(height[l],height[r])*(r-l);
        while(l!=r)
        {
           
            if(height[l]<height[r])
                l++;
            else
                r--;
            if(ans<min(height[l],height[r])*(r-l))
                ans=min(height[l],height[r])*(r-l);
        }
        return ans;
    }
};