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 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;
}
}
没有评论:
发表评论