【LeetCode】11. Container With Most Water

Givennnon-negative integersa1,a2, ...,an, where each represents a point at coordinate (i,ai).nvertical lines are drawn such that the two endpoints of lineiis 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 andnis at least 2.
に言及
与えられたのはx軸に垂直な直線で、x軸に囲まれた面積が最小になるように2本の直線を求めます.
だから問題は1つの矩形に変換して1本の辺は縦座標の小さいあの根を取って、1本の辺は横座標の差を取って、この矩形の面積が最大であることを求めます(最初は台形だと思って、明らかに論理的ではありません).
答え
自分で半日考えたのは、行き先から遍歴し、height[i]を高い矩形の最大値としてn回遍歴すればいいということです.
two pointerを定義します.1つはm=0で、1つはn=size-1で、現在のheight[i]より大きい最初の値(++m;--n)を見つけます.max(i-m,n-i)*height[i]はheight[i]を高い矩形の最大値に違いありません.n個を比較して最大をとると得られる.この時間は複雑度はまだo(n^2)ですが、剪定があるのでパスしました.
.しかし、その後、答えをめくると、もっと簡単な考えがある.底辺が長く、two pointer、一つはm=0、一つはn=size-1で、初めてmin(m,n)を辺とする面積を計算した.そしてm,nの小さい辺を移動し,m−1を高い矩形の値を算出した.
最初のコード:

class Solution {
public:
    int maxArea(vector& height) {
        int max=0;
        for(int i=0;ii&&height[n]n-i)?i-m:n-i);
            if(tmp>max1) max=tmp;
        }
        
        return max;
    }
};

より優れたコード:

class Solution {
public:
    int maxArea(vector& height) {
        int max=0;
        int m=0,n=height.size()-1;
        while(mmax?tmp:max;
            if(height[m]height[n])--n;
            else {++m; --n;}
        }
        
        return max;
    }
};