2015年9月17日星期四

Leetcode 11 Container With Most Water

Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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 1: Use 2 pointers, i & j initially from beginning and end of array. Current container with water is Math.min(height[i], height[j]) * (j - i), if i is the lower bar, move j back will make it even less water, so we should i++; reversely if j is the lower bar, we should move j--;
 public class Solution {  
   public int maxArea(int[] height) {  
     int n=height.length;  
     int i=0, j=n-1;  
     int res=0;  
     while (i<j) {  
       res=Math.max(res,Math.min(height[i],height[j])*(j-i));  
       if (height[i]<height[j]) i++;  
       else j--;  
     }  
     return res;  
   }  
 }  

没有评论:

发表评论