This is the 25th day of my participation in the August Challenge

preface

Today to an interesting algorithm – fill up the container of water, see the topic I was thinking about the short board effect seen before also called barrel principle, the principle is that you most does not depend on your buckets of water are the longest, and depends on the shortest board buckets, ha, ha, ha, not much said, directly on the subject.

Topic describes

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.

Example 1:

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

Output: 49

Explanation: the vertical lines 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 2:

Enter: height = [1,1]

Output: 1.

Example 3:

Enter: height = [4,3,2,1,4]

Output: 16

Example 4:

Enter: height = [1,2,1]

Output: 2

Their thinking

  • The main idea of this problem is that the maximum capacity of water depends on the shortest column
  • The solution to this problem is to use a double pointer, one pointing to the head of the array, one pointing to the tail of the array, judge the product of the minimum value in the left and right Pointers and the distance between the two Pointers, then determine which value is smaller, discard the smaller, and move the pointer
  • Let’s say the distance between the left and right Pointers is t, and math.min (x,y)*t, and let’s say x<=y, then no matter how y moves, the new capacity is going to be smaller than the original capacity, because t is getting smaller, and x is not changing. Okay
  • Now we can get rid of where the left pointer was, which is to move the left pointer
  • That is, when a point compares two Pointers to a number, the smaller number is destined not to be the largest bound, as shown in the following code
/ * * *@param {number[]} height
 * @return {number}* /
var maxArea = function(height) {
    let left = 0 
    let right = height.length-1
    let maxCapacity = 0// Maximum capacity
    let capacity = 0// The capacity after each move
    while(left < right){
        capacity = Math.min(height[left],height[right])*(right-left)
        maxCapacity = Math.max(maxCapacity,capacity)
        if(height[left]<height[right]){
            left++
        }else{
            right--
        }
    }
    return maxCapacity
};
Copy the code

LeetCode run result

conclusion

This question is very interesting, not only an algorithm, but also very philosophical, try to go forward, gogogo