Sunday, December 28, 2014

Container With Most Water (LeetCode Array)

Question:  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.

Idea: Use two pointers to maintain a sliding window. For each window, get its area and compare with the result. The window starts with the maximum width (0, length-1). If the height[left] is smaller than height[right], move the left pointer forward (vice era). This is because moving the pointer will decrease the width. If we keep the min(heigh[left],height[right]) in the next comparison, the area size can not be larger than the current. So we just need to move the shorter of the two pointers.

Time: O(n) Space: O(1)

Code: 
 public class Solution {  
   public int maxArea(int[] height) {  
     if(height==null||height.length<=1)  
       return 0;  
     int i=0;  
     int j=height.length-1;  
     int result=0;  
     while(i<j)  
     {  
       result=Math.max(result,(j-i)*Math.min(height[i],height[j]));  
       if(height[i]>height[j])  
         j--;  
       else  
         i++;  
     }  
     return result;  
   }  
 }  

No comments:

Post a Comment