Container With the Most Water

A row of vertical walls stands one unit apart, and heights[i] is the height of wall i. Pick any two walls: together with the ground they form a container, and water fills it up to the top of the shorter wall. Walls in between do not get in the way. Write max_water(heights) that returns the most water any two walls can hold, measured as the distance between them times the water's height. With fewer than two walls, return 0.

Examples

max_water([2, 7, 3, 6, 4, 8, 1])   # returns 28
max_water([5, 5])                  # returns 5
max_water([1, 2, 3, 4, 5])         # returns 6

In the first example the walls of height 7 (index 1) and 8 (index 5) stand 4 apart, and the shorter is 7, so they hold 4 * 7 = 28.

Constraints

• 0 <= len(heights) <= 100,000
• 0 <= heights[i] <= 10,000

Note

Trying every pair works for short rows, but 100,000 walls make about 5 billion pairs. Aim for a way that looks at each wall only a few times.