[LeetCode]Container With Most Water

[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.

題意：假設有一個x,y的二維坐標，我們定義area(i,j) = min(xi,xj) * |i - j, 找出最大的area。
思路：用兩個指針l,r分別指向數組兩邊，然後計算當前area，接著比較xl,xr大小，小的那個的下標變化。知道l>=r|。 這是由於當前的矩形寬度是最大的，那麼接下來的矩形想想面積比當前的面積大，就只能夠增加矩形的高。算法復雜度為O(N)
代碼：

    public int maxArea(int[] height) {//O(N)
        int max = 0;
        int curr  = 0;
        int l = 0, r = height.length - 1;
        while (l < r){
            curr = Math.min(height[l],height[r]) * (r - l);
            max = Math.max(max, curr);
            if(height[l] < height[r]){
                l ++;
            }else if(height[l] > height[r]){
                r  --;
            }else {
                l ++;
                r  --;
            }
        }
        return max;
    }