Topic (LeetCode Question Bank 11)

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. Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Example 1:

,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.

Example 2:

Input: height = [1,1

Example 3:

Input: height = [4,3,2,1,4

Example 4:

Input: height = [1,2,1

Answer key

Subject analysis

To get this problem, we first analyze it from a mathematical point of view, to calculate the maximum water capacity, that is, the maximum area of the rectangle composed of two columns and coordinate axes. Let’s first write out the calculation formula:

  // left represents the subscript of the left column, right represents the subscript of the right column, and the difference is the length of the rectangle
  // The width is rectangular with the low column
  max = (right - left) * Math.min(height[left], height[right])
Copy the code

The formula above basically confirms that the method we’re going to use is a double pointer.

  • The critical point here is: left < right

  • Reserve maximum value the maximum value is taken for each calculation

      max = Math.max(max, ((right - left) * Math.min(height[left], height[right])))
Copy the code

  • How do we move this is the most important step, how do we move the pointer? Because no matter which side we move, our length gets shorter. In the case of constant length, to maximize the area, we should keep the tall columns. That is, one more step:

      if(height[left] > height[right]) {
    right --;
  } else  {
    left ++;
  }
Copy the code

    Let’s combine the above formulas and write it like this:

    max = Math.max(max, ((right - left) * (height[left] > height[right] ? height[right--] : height[left++])))
Copy the code

    So we’re done with the core of our algorithm.

The complete code
/ * * *@param {number[]} height
 * @return {number}* /
var maxArea = function(height) {
    let left = 0;
    let right = height.length-1;
    let max = 0;
    while(left < right) {
        max = Math.max(max, ((right - left) * (height[left] > height[right] ? height[right--]: height[left++])));
    }
    return max;
};
Copy the code