本文共 1197 字，大约阅读时间需要 3 分钟。

思路：

自己想到了一个算法复杂度为n平方的算法。放到oj上是超时的。因为我只是在最简单的方法上做了一点点优化。就是左端点向前移动的时候，如果下一个数比当前数小那么直接跳过。原因是，下一个数如果小了，那么桶高度一定减小，并且桶宽度也减小，可以直接过。

public class Solution {    public int maxArea(int[] height) {       int maxWater=0;        int i=0;        while(i
   
    i;j--)            {                maxWater=Math.max(maxWater, (j-i)*Math.min(height[i],   height[j]));            }            int nextIndex=i+1;            while(nextIndex
    
     =height[nextIndex])                {                    nextIndex++;                }                else                {                    break;                }            }            i=nextIndex;        }        return maxWater;    }}
    
   

但是看了他们都是用线性算法解决的，所以还是挺崇拜他们的。

public class Solution {    public int maxArea(int[] height) {      int left=0;        int right=height.length-1;        int maxWater=0;        while(left

这是一个线性时间的算法。每进行一次循环那么左边向前或者右边向后。

这么做的原因有一下几点 1水的多少取决于桶的高度。所以我们在移动边界的时候如果移动大的，那么捅的容量一定减小。 2至于为啥可以每次都可以确定不要一个边界，可以做如下反证法

我们不妨假设右端有短边被淘汰了的A。现在左端是一个非常大的边B。

如果A和B组成的桶非常大。那么这里实际起作用的边是A的高度。这是形成的容积为V

这是不妨假设，既然A被淘汰了。那么证明在遇到B之前，左边一定有一个边是高于A的，不妨设为C。此时C与A组成的桶起作用的高度还是A，但是C距离A比B远，此时桶的容积V2是大于V的。

而V2已经计算过了，可能已经与MAXV做过比较，所以我们每个边只需要一次比较就可以，我们可以放心的排除A边

转载地址：http://iduvb.baihongyu.com/