Container With Most Water [leetcode 11]

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.

 

这个题目苦思冥想半个下午,还是想不到正确解法,除了1/2 * N^2的,就没有了,看到了标准解法之后,证明了半个小时,总算明白了,借来的答案如下
,可以看到,就是首先选择最边上的两个,然后将其中短的向内移动,寻找更大的面积,因为如果这个时候,如果选择移动右边的长边,无论如何得到的面积,都不可能超过目前的面积MAX,因为面积(a-b) * min(sa,sb),既然目前a-b达到最大,min(sa , sb) = sa ,无论如何移动sb,得到sb1,如果sb1 > sa, 在a-b1减小的情况下,min(sa,sb1) = sa,面积依旧是减小,如果sb1 < sa,那么sb1 * (a-b1) < sb1 (s – b) < sa(a-b),所以移动长的边,无论如何都不能得到更大的,贪心的移动小边,寻找可能的更大的,

这里有一个问题,就是贪心的寻找得到的更大的,却未必是最大的,这个就是贪心的问题,

ok,现在就需要证明,一定不会错过最大面积的组合sa,sb,

我们假定在下面贪心的样例中第一个遇到的最大组合边(O(n)扫,每个边至少都被访问一次)为sa,那我们需要证明,在已经得到sa的情况下,程序一定会移动另一个边到Sb.

我们假定,当移动到sa的时候,另一个边为sc,那么如果想将sc移动到sb,必然有sa > sc,利用反证法,sc > sa 是不可能的,  因为 a – c > a – b ,而且sa,sb是最大组合,min(sa, sb) * a- b  > min(sa,sc) * a – c 所以然有min(sa, sb) > min(sa, sc),也就是min(sa,sb) > sa, 这个是不可能的,和sa,sb是最大面积的设定冲突,所以必然有sa > sc ,根据程序运行,sa保留,sc向内移动,寻找到sb,得到最大的,min(sb,sa) * (a – b) 是最大值,

 

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

Leave a comment

Your email address will not be published.

*