11. Container With Most Water - cocoder39/coco39_LC GitHub Wiki

11. Container With Most Water

Proof: suppose area[low, high] indicates the area of container with low and high. suppose height[low] < height[high], then we move low to low+1, that means we ignore area[low, high-1],area[low, high-2],etc, if this is safe, then the algorithm is right, and it's obvious that area[low, high-1],area[low, high-2]...... can't be larger than area[low, high] since its width can't be larger than high-low, and its height is limited by height[low].

public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int res = 0;
        while (i < j) {
            int h;
            int l = j - i;
            if (height[i] < height[j]) {
                h = height[i];
                i++;
            } else {
                h = height[j];
                j--;
            }
            res = Math.max(res, h * l);
        }
        return res;
    }