Today we share a goose factory interview question. Let’s cut to the chase.

01. Examples of topics

This topic will friends may feel very simple, but I think this topic is really classic, so I still have to take it out. There is also an advanced version of “catch rain”, which will be explained later.

The container that holds the most water
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, and the value of n is at least 2.The vertical lines in the figure represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.


Example:

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

02. Topic analysis

It can be observed that the two vertical line segments will form a rectangular area with the coordinate axis, the length of the shorter line segment will be the width of the rectangular area, and the distance between the two lines will be the length of the rectangular area. We solve the maximum water capacity, in fact, to find the maximum area of the rectangle.

First of all, the problem can be solved by brute force, by finding each possible pair of line segments, and then finding the maximum area in those cases. I’m going to skip this, but if you’re interested, you can go down and try it yourself. This problem is more classic is to use a double pointer to solve, will have friends may wish to review review.


Suppose our array is: [1 8 6 2 5 4 8 3 7], it looks like this:

First, we initialize two Pointers to each side to form our first rectangular region.


We tried to move the long side to the short side and found that it did not make any sense to increase the area. Here’s an example:


So we choose to move the short side to the long side. According to the barrel principle, the height of water depends on the short side.


Continuing the process, we always choose to move the short side to the long side. And in each movement, we record the current size of the area. (Below these pictures, I take a PPT to do….)






Until the two sticks hit each other.


Based on the analysis, get the code :(turn to the Java brand)

//JAVA 
class Solution { 
    public int maxArea(int[] height) { 
        int i = 0, j = height.length - 1, res = 0; 
        while(i < j){ 
 res = height[i] < height[j] ?  Math.max(res, (j - i) * height[i ]):  Math.max(res, (j - i) * height[j--]);  }  return res;  } } Copy the code

Proof by contradiction

I might have friends who want me to prove it. In fact, I think it’s a barrel principle. The Bucket Principle: How much water a bucket can hold depends on its shortest piece of wood.


Proof by contradiction:

area = h(m) * w

Move n to n, if n is shorter than m, then:

area = h(n) * (w-1)

There are area < area


Move n to n, if n is longer than m then:

area = h(m) * (w-1)

There are area < area


So, did you learn today’s quiz question? Leave your thoughts in the comments section!

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download