11. Container With Most Water.md

11. Container With Most Water

Problem

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.

tag:

Solution

贪心策略：

用两个指针i,j指向头和尾，每次迭代， 如果height[i]<height[j], i++, 否则，j--， 并更新最大容量； 直观的想， 缩小宽度， 只有高度增加才有可能得到更大的容量

证明：

Here is the proof. Proved by contradiction:

Suppose the returned result is not the optimal solution. Then there must exist an optimal solution, say a container with aol and aor (left and right respectively), such that it has a greater volume than the one we got. Since our algorithm stops only if the two pointers meet. So, we must have visited one of them but not the other. WLOG, let's say we visited aol but not aor. When a pointer stops at a_ol, it won't move until

The other pointer also points to aol. In this case, iteration ends. But the other pointer must have visited aor on its way from right end to aol. Contradiction to our assumption that we didn't visit aor.

The other pointer arrives at a value, say arr, that is greater than aol before it reaches aor. In this case, we does move aol. But notice that the volume of aol and arr is already greater than aol and aor (as it is wider and heigher), which means that aol and aor is not the optimal solution -- Contradiction!

java

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

go

func maxArea(height []int) int {
	max := 0
	for i, j := 0, len(height)-1; i < j; {
		max = max(max, (j-i)*max(height[i], height[j]))
		if height[i] < height[j] {
			i++
		} else {
			j--
		}
	}
	return max
}