This is the 15th day of my participation in Gwen Challenge

Topic describes

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. Leetcode-cn.com/problems/co…

/ / sample 1Input:1.8.6.2.5.4.8.3.7] output:49Explanation: 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) is49./ / sample 2Enter: height = [4.3.2.1.4] output:16
Copy the code

The label

Double pointer

Analysis of the problem solving

1. Double pointer

Let’s get right to it.

When we look at this topic, we first confirm two things.1.When calculating the area of water, the width and height of cuboid is always the smallest height of the two vertical lines.2.The length of a cuboid is the difference of two vertical lines. When recording the relationship between each piece of data in a data set and the rest of the data, the most correct solution is to go directly to the double pointer. Let's just take an example array. n = [1.8.6.2.5.4.8.3.7] set the maximum area to res =0Set two left and right Pointers corresponding to the first and last pointer to the array data. l =0  r = 8Move the pointer the first time. So the first thing we need to do is figure out whether the width of the area is the left perpendicular or the right perpendicular. And then we have to figure out if the left vertical line is smaller than the right vertical line and if it is we take the left vertical line as the width1, as long as the distance between two Pointers7, and compare the area with res to save the maximum area, res =Math.max(res(0), newRes(1 * 7Finally, we move the small side of the pointer. l = l +1If it is not, we take the width of the right vertical line as the width, calculate the area and compare with the previously saved RES to get the maximum area. Notice here why did I move the short vertical line?1.Moving the pointer inward, no matter moving the long vertical line or the short vertical line, will make the cuboid length smaller.2.If you move the long vertical line, no matter if the next vertical line becomes smaller or stays the same, the cuboid will have a smaller area than the previous one, so it won't make sense. Therefore, if we move the pointer of the short vertical line, the area of the next cuboid may be larger than that of the current cuboid. And then finally, we find the size of each area, and we just output the largest one.Copy the code

Go to ！！！！！

function maxArea(height: number[]) :number {
   // create the left pointer l, right pointer r, area res
   let l = 0, r = height.length - 1, res = 0
   When the left pointer is smaller than the right pointer, move the pointer. When the left pointer and the right pointer move to the same position, the double pointer traversal ends.
   while (l < r){
       // If the left perpendicular is smaller than the right perpendicular
       if(height[l] < height[r]) {
           // Compare the original area res with the shortest vertical line * the distance between the two vertical lines = the area of the new cuboid
           res = Math.max(res,  (r - l) * height[l])
           // Move the pointer to the short left vertical line for next area comparison.
           l++
        }
       else {
           // Same logic, if the left vertical line is larger than the right vertical line, then the right vertical line is wider to calculate the area ratio.
           res = Math.max(res,  (r - l) * height[r])
           r--
       }
   }
   return res
};
Copy the code

The last

Not pigeon from today, every day an algorithm problem and published articles, the first to solve the problem group for Top100, the seventh topic finished work!!