leetcode 11. Container With Most Water

2017-08-16

题意

给定一个非负数组(a1,a2,a3…)。假定这对数组对应了坐标轴的y轴，下标1 2…对应了x轴。从(i,0)至(i,ai)画一条直线。寻找这么两条线，使得两条线和x轴组成的容器容量最大。

我的思路

简单想到暴力法：遍历所有的两条线组合即可得到。

暴力解法

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = Integer.MIN_VALUE;
        for(int i=1;i<=height.length-1;i++){
            for(int j=i+1;j<=height.length;j++){
                int maxtemp = Math.min(height[i-1],height[j-1])*(j-i);
                if(maxtemp>maxarea) maxarea = maxtemp;
            }
        }
        return maxarea;
    }
}

这个解法是会超时的。

如何优化？

大神思路

首先定义两端分别指向数组开始和结尾，移动较短的那个。比如开始那个短就往后走，如果结尾那个短就往前走。记录最大值。

想想这样为啥能找到面积的最大值？

仔细想想，两条线之间的面积最大，如果移动的是较长的那个，是不是意味面积肯定不增长，因为容器的容量被较短的那条线限制了。但是移动较短的一端可能得到较大的。也就是说尽量减少了宽度，遇到较长的线段仍然可以使得面积变大。

具体的原理：
假定数组为长度为6，画出一个简易的矩形，每一行表示第一条线，每一列表示第二条线（两条线组成的容量）。x表示不需要计算的：1.对角线上两条线是重叠的。2.下三角和上三角是完全对称的。不需要重复计算。

好了，先开始计算(1,6)，用o表示计算出的容量。假定1的线条较短，因为移动较长的线段不可得到比当前(1,6)更大的结果。也就是说(1,2)….(1,5)都不需要计算了。我们用’- - -‘表示不需要计算的。

1 2 3 4 5 6

1 x - - - - o

2 x x

3 x x x

4 x x x x

5 x x x x x

6 x x x x x x

因为1比较短我们移动到2，计算(2,6)。同样’|’表示不需要计算的，

1 假设6这条线较短。就变成了(2,5)。
2 如果5这条线较短，接着计算出(2,4)。
3 如果2比较短，接着去计算(3,4)。
根据上述的步骤计算的所有o和不需要计算的组成了整个上三角，所以会得到最大的面积。

1 2 3 4 5 6

1 x - - - - o

2 x x - o o o

3 x x x o | |

4 x x x x | |

5 x x x x x |

6 x x x x x x

优化代码

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

最快的代码

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