Given

nnon-negative integersa1,a2, …,an, where each represents a point at coordinate (i,ai).nvertical lines are drawn such that the two endpoints of lineiis 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.

## Analysis

It could take a long time if you check every possible container, because the time complexity is $O(n^2)$. So we need another way to achieve it.

We can use two pointers pointing to left and right. Calculate the area formed by left and right pointer. If height of left is smaller than right, we will move left pointer one step, otherwise we will move the right pointer left 1 step. The maximum area is saved during the processing.

When we move the pointer, the width of the area decrease. If the height is smaller than the previous height, then it’s impossible that the area will increase. In other words, if left is shorter than right, no matter how you move your right pointer, you can’t find a area larger than it.

## Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class Solution { public int maxArea(int[] height) { if (height.length <= 1) return 0; int max = 0; int left = 0; int right = height.length - 1; while (left < right) { max = Math.max(max, (right - left) * Math.min(height[left], height[right])); if (height[left] < height[right]) left++; else right--; } return max; } } |

## Complexity

The complexity of this algorithm is $O(n)$.