The problem

Give you n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

Note: You cannot tilt the container.

​

,8,6,2,5,4,8,3,7 input: [1] output: 49 explanation: the figure in the vertical line represents the input array,8,6,2,5,4,8,3,7 [1]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.Copy the code

Train of thought

First response, brute force, running through all the possibilities, order n2. It’s definitely not going to work, so we need to find a pattern.

We now have two Pointers, one to the first and one to the last.

Let’s say the first height is H1, and the last height is Hn, H1 is greater than Hn, so what’s the area they’re covering?

Hn times n minus 1.

Now we want one of the Pointers to move inward, and maybe the area will go up. We think that the area depends on the distance between the two columns and the shortest of the two columns. Now, as we move inward, the relative distance of the two Pointers to the column becomes shorter. In order to increase the area, we have to choose to make the shorter of the two columns longer, so we have to move the pointer to the shorter column.

Loop the above operation, the two Pointers meet to end the loop, complete the traversal.

So, after analysis and the introduction of dual Pointers, the time complexity goes from O(n2) to O(n).

code

var maxArea = function(height) {
    let frontPoint = 0;
    let endPoint = height.length - 1;
    let max = 0;
    while (frontPoint < endPoint) {
        max = Math.max(max, (endPoint - frontPoint) * (height[frontPoint] > height[endPoint] ? height[endPoint--]: height[frontPoint++]))
    }
    return max;
};
Copy the code

​