container-with-most-water

Given n non-negative integers a₁ , a₂ , ..., a_n , where each represents a point at coordinate (i, a_i ). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i ) 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.

在二维坐标系中，(i, ai) 表示 从 (i, 0) 到 (i, ai) 的一条线段，任意两条这样的线段和 x 轴组成一个木桶，找出能够盛水最多的木桶，返回其容积（这里只算面积）

一：穷举

刚发现牛课上的leetcode测试用例可能不一样（穷举能过） /**他这题目应该是求面积 * 穷举法 * Created by a819 on 2017/8/7. */ public class Solution { //private static final double PI=3.14; public int maxArea(int[] height){ int len=height.length; if(len<2) return 0; int max=0;//最大容积 int h=0;//高 //double r=0; for(int i=0;i<len;i++) { for (int j=0;j<len;j++) { //r=Math.abs(j-i)/2; h=(height[i]<=height[j])?height[i]:height[j]; //double area=PI*r*r*h; int area=Math.abs(i-j)*h; if(area>max) { max=area; } } } return max; } /* public static void main(String[] args) { int []a=new int[]{5,7,5,6,1,3,8,9,1}; Solution s=new Solution3(); int b=s.maxArea(a); System.out.println(b); } */ }

二：O（n）

网上比较好的解题思路

由于桶是以最小高度和底边长的直径，例如：当左边小于右边高度时，面积都是以左边高度算面积，此时底边直径最大，左边与当前右边的其他情况不考虑，所以直接记录面积将左边右移。

/**O(n) * Created by a819 on 2017/8/7. */ public class Solution { public int maxArea(int[] height){ int i=0,j=height.length-1; int area=0,max=0; if(height.length<2) return 0; while(i<j){ if (height[i] >=height[j]) { area=height[j]*(j-i); if (area>max) max=area; j--; } else{ area=height[i]*(j-i); if (area>max) max=area; i++; } } return max; } }