“This is the 22nd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Look a hundred times beauty, beauty is not necessarily yours. But if you run the algorithm a hundred times, the knowledge is yours

Who can have nine floors? No need to get up!

Title address

The title

Give you n non-negative integers A1, A2… , a ‘ ‘n, 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: [1,8,6,2,5,4,8,3,7] output: 49 explanation: 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.Copy the code

Example 2:

Input: height = [1,1Copy the code

Example 3:

Input: height = [4,3,2,1,4Copy the code

Example 4:

Input: height = [1,2,1Copy the code

Tip:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

Their thinking

  • So let’s do this with a double pointer
  • We define two Pointers, one that looks up from front to back, and the other one that does the opposite and shrinks back to front that is, from both ends to the center
  • The maximum size depends on the width of the container (the index interval between two Pointers) and the height of the short edge
  • When the edge of a pointer is short, it shrinks to the center
  • Here we explain why we move the short side: When we move the short side, the short side might get higher and make the container bigger and therefore the volume bigger. Right
  • On the other hand, because the volume depends on the short side, if you move the long side the height doesn’t change, which means the volume doesn’t change
  • Update the maximum volume
  • And finally we’re going to output the maximum that we can hold

The problem solving code

var maxArea = function(height) {
    let maxArea = 0
    for(let i =0,j = height.length-1; i<j;) {letminHight = height[i]<height[j]? height[i++]:height[j--] maxArea =Math.max(maxArea,minHight*(j-i+1))  // Update the maximum value
    }
    return maxArea
};
Copy the code

If you have any questions or suggestions, please leave a comment!