11. Container With Most Water leetcode Java

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.

Solution:

Two pointer and greedy

We maintain two pointer: left, right. if height[left]<height[right], move right pointer(right--) won't make the area bigger, because the height of the container is determined by shorter one. In this case area=height[left]*(right-left), move right pointer can only make height unchanged(height[new right]>=height[left]) or even shorter(height[new right]<height[left]). So in this case the only possible way to make the area bigger is move the left pointer(left++) and till the height is increased. Vice verse. 

The time complexity: O(n)

   public int maxArea(int[] height) {  
    if(height==null || height.length<2) return 0;  
    int l=0;  
    int r=height.length-1;  
    int maxA=(r-l)*Math.min(height[l],height[r]);  
    while(l<r){  
      if(height[r]<=height[l]) r--;  
      else l++;  
      maxA=Math.max(maxA,(r-l)*Math.min(height[l],height[r]));  
    }  
    return maxA;  
   }