LeetCode(11):Container With Most Water

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表示木板所处的位置，找到两个木板使两个木板之间的容量最大。

思路：采用双指针，left,right分别指向数组的首元素和末尾元素，因为容量的计算公式为（right - left）*min(height[left],height[right])，刚开始的时候是宽度最大（right-left）要想增大容量，宽度缩短了，所以，要选择高度较高的木板才能增大容量，这种情况下要保留木板高度大的一方，然后另一方移动。

代码：

public int min(int i,int j)
  {
    return i<j?i:j;
  }
public int maxArea(int[] height) {
        int cap = 0;
        int left = 0,right=height.length -1;
        while(left<right){
            int water =  min(height[left],height[right])*(right-left);
            if(water>cap) 
                cap = water;
             
            if(height[left]<height[right]){
                left ++;
            }else{
                right--;
            }
        }
        return cap;
    }

LeetCode(11):Container With Most Water

原文：http://www.cnblogs.com/Lewisr/p/5161406.html