# Question

Formatted question description: https://leetcode.ca/all/11.html

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.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

@tag-array



# Algorithm

The following is an example: [4,6,2,6,7,11,2] to explain.

1 . First, suppose we find the vertical line that can take the maximum volume as i, j (assuming i<j), then the maximum volume C = min( ai, aj) * (j- i);

2 . Below we look at such a property:

• No line at the right end of j will be higher than it! Suppose there is k |( j<k && ak> aj), then ak> aj, so min(ai,aj, ak) =min(ai,aj), so the volume of the container formed by i, k C’= min(ai,aj) * (ki)> C, which is the most contradictory value with C, so there will be no line higher than it behind the proof j; To
• Similarly, there will be no higher line on the left side of i; To What is this indicating? If we currently get the candidate: set x, y as two lines (x< y), then the two new edges that can be larger than it must be in the interval [x,y] And ax’> =ax, ay’>= ay;

3 . So we move closer from the two ends to the middle, and update the candidate values ​​at the same time; when shrinking the interval, first shrink from the smaller edge of x, y;

The intuitive explanation is: volume is area, which is affected by length and height. When the length decreases, the height must increase to increase the area, so we start to decrease from the longest length, and then look for a higher line to update Alternate

Java