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