装最多水的容器

1、暴力解决，双层循环，每一次算一个值找最大
2、但是复杂度较高

import java.util.*;


public class Solution {
    /**
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    private int fun(int[] height,int left,int right){
        return Math.min(height[left],height[right])*(right-left);
    }
    public int maxArea (int[] height) {
        // write code here
        int max=0;
        for(int i =0;i<height.length;i++){
            for(int j =i+1;j<height.length;j++){
                max = Math.max(max,fun(height,i,j));
            }
        }
        return max;
    }
}

//设置left、right两个下标，代表左右两条直线，从两端开始遍历，对于两条直线和X轴所形成的的容器，若左边的直线高度大于右边的直线高度，则右边直线下标right--,反之左边下标直线下标left++。
//因为容器所成盛水的体积等于宽度（right-left）乘以较低的直线高度，淘汰较低的直线高度，尝试寻找更高的直线高度，继而尝试寻找更大的体积。
public class Solution {
    public int maxArea(int[] height) {
        if(height == null || height.length == 0)
            return 0;
        int left = 0;
        int right = height.length - 1;
        int max_area = 0;
        int area = 0;
        while(left < right){
            if(height[left] > height[right]){
                area = height[right] * (right - left);
                right--;
            }
            else{
                area = height[left] * (right - left);
                left++;
            }
            if(area > max_area){
                max_area = area;
            }
        }
        return max_area;
    }
}

/**
 * 
 * @author ChopinXBP
 * 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 and n is at least 2.
 * 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * 说明：你不能倾斜容器，且 n的值至少为 2。
 *
 */

public class ContainerWithMostWater {     public static void main(String[] args) {         // TODO Auto-generated method stub         int[] height = {1,8,6,2,5,4,8,3,7};         int[] height2 = {1,2,4,3};         System.out.println(maxArea(height));         System.out.println(maxArea(height2));         System.out.println(maxArea2(height));         System.out.println(maxArea2(height2));     }     //对每一条线段i，找左右两端距离i最长的不小于i的长度的线段j。j作为长，i作为宽，ij构成的矩形是包含线段i的面积最大的矩形。
    public static int maxArea(int[] height) {
        int result = 0;
        
        for(int i = 0; i < height.length; i++) {
            int num = height[i];
            int longest = 0;
                         int idx = 0;
            while(idx < i) {
                if(height[idx] >= num) {
                    longest = i - idx;
                    break;
                }
                idx++;
            }
            idx = height.length - 1;
            while(idx > i && idx - i > longest) {
                if(height[idx] >= num) {
                    longest = idx - i;
                    break;
                }
                idx--;
            }
                         if(num * longest > result) {
                result = num * longest;
            }
        }
        
        return result;
    }
    
    //设置left和right从两端逼近，每次计算其和较短边围成的矩形的面积，之后移动较短边。逼近过程中最大的矩形面积即为所求。
    public static int maxArea2(int[] height) {
        int result = 0;
        
        int right = height.length - 1;
        int left = 0;
        
        while(left < right) {
            int shorter = height[right] < height[left] ? height[right] : height[left];
            if((right - left) * shorter > result) {
                result = (right - left) * shorter;
            }
            //每次移动较短边（移动较长边可能会导致下一个矩形因为短边限制取不到最优）
            if(height[right] < height[left]) {
                right--;
            }else {
                left++;
            }
        }
        
        return result;
    }
}

	

 

从两边开始向中间转换

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

//没有理解，求大神理论证明一下，为什么？
public class Solution {
    public int maxArea(int[] height) {
        int result = 0;
        for (int i = 0, j = height.length -1; i < j; ) {
            result = Math.max(result, Math.min(height[i], height[j]) * (j - i));
            if (height[i] > height[j]) j--;
            else i++;
        }
        return result;
    }
}

AKA, the general idea to find some max is to go through all cases where max value can possibly occur and keep updating the max value. The efficiency of the scan depends on the size of cases you plan to scan.
To increase efficiency, all we need to do is to find a smart way of scan to cut off the useless cases and meanwhile 100% guarantee the max value can be reached through the rest of cases.

In this problem, the smart scan way is to set two pointers initialized at both ends of the array. Every time move the smaller value pointer to inner array. Then after the two pointers meet, all possible max cases have been scanned and the max situation is 100% reached somewhere in the scan. Following is a brief prove of this.

Given a1,a2,a3.....an as input array. Lets assume a10 and a20 are the max area situation. We need to prove that a10 can be reached by left pointer and during the time left pointer stays at a10, a20 can be reached by right pointer. That is to say, the core problem is to prove: when left pointer is at a10 and right pointer is at a21, the next move must be right pointer to a20.

Since we are always moving the pointer with the smaller value, i.e. if a10 > a21, we should move pointer at a21 to a20, as we hope. Why a10 >a21? Because if a21>a10, then area of a10 and a20 must be less than area of a10 and a21. Because the area of a10 and a21 is at least height[a10] * (21-10) while the area of a10 and a20 is at most height[a10] * (20-10). So there is a contradiction of assumption a10 and a20 has the max area. So, a10 must be greater than a21, then next move a21 has to be move to a20. The max cases must be reached.

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

	return maxArea;
}

/**
从两边向中间计算
**/
public class Solution{
	public int maxArea(int[] height) {
		int result = 0;
		int left = 0;
		int right = height.length-1;
		int temp = 0;
		while (right!=left) {
			
			temp = (right-left)*Math.min(height[left], height[right]);
			if (temp>result) {
				result = temp;
			}
			if (height[left]>height[right]) {
				right--;
			}else {
				left++;
			}
		}
		return result;
    }

}