LeetCode: Container With Most Water 解题报告

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.

SOLUTION 1:

采用2个指针一个在左一个在右，计算『桶』可以容纳的水。如果左边低，则左指针右移（试图看可不可以找到更高的bar），反之左移右指针 

证明：

当H[l] < H[r]的时候，为什么可以移动左指针呢？

因为以l为边界的最大值我们已经计算出来了，它是一个短板，把r往左移不可能得到更大的蓄水量。所以以l为边界的可以结束计算了。直接把l右移即可。

引自http://www.cnblogs.com/TenosDoIt/p/3812880.html 的证明：

正确性证明：由于水的容量是有较小的那个边界决定的，因此某次迭代中，假设height[i] < height[j]，那么j 减小肯定不会使水的容量增大，只有i 增加才有可能使水的容量增大。但是会不会有这种可能：当前的i 和 某个k (k > j)是最大容量, 这也是不可能的，因为按照我们的移动规则，既然右指针从k 移动到了j，说明i 的左边一定存在一个边界 m，使m > k，那么[m, k]的容量肯定大于[i, k]，所以[i,k]不可能是最大容量。可以参考here

public class Solution {
    public int maxArea(int[] height) {
        if (height == null) {
            return 0;
        }
        
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int area = h * (right - left);
            maxArea = Math.max(maxArea, area);
            
            if (height[left] < height[right]) {
                // 如果左边界比较低，尝试向右寻找更高的边界
                left++;
            } else {
                // 如果右边界比较低，尝试向左寻找更高的边界
                right--;
            }
        }
        
        return maxArea;
    }
}

2014.1229:

public class Solution {
    public int maxArea(int[] height) {
        if (height == null) {
            return 0;
        }
        
        int len = height.length;
        int l = 0;
        int r = len - 1;
        
        int max = 0;
        while (l < r) {
            int h = Math.min(height[l], height[r]);
            int w = r - l;
            max = Math.max(max, h * w);
            
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        
        return max;
    }
}

代码：

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/twoPoints/MaxArea.java