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 and n is at least 2.
</br>
Solution
As we know, the volume of the water is determined by the height and the width of the container, and height is restricted by the shorter line of the container.
Suppose we start by two pointer at each side of the array, if we want to expand the area, we should not move the longer line as the height is restricted by the shorter one.
Instead, we can move the shorter line to increase the height. Since we start from two side of the array, we begin with the maximum width so we do not have to worry about the potential area increase when moving line inwards.
Consider this: we start with
[most_left, most_right]
The width is (n-1) - 0
//The biggest width can be achieved
So, if we move the longer line of these two, not only will we lose the width, but also gain no increase in height. Hence, we can ignore this movement.
And there is nothing tricky left, the code is self-explained.
Java
public class Solution {
public int maxArea(int[] height) {
int min_height = 0, area = 0;
int i = 0, j = height.length - 1;
while (i < height.length && j >= 0){
if (height[j] > height[i]){
area = Math.max(area, height[i] * (j-i));
i++;
}
else {
area = Math.max(area, height[j] * (j-i));
j--;
}
}
return area;
}
}
</br>
