11. Container that holds the most water

The title

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: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.Copy the code

Answer key

Double pointer

  • We know that the capacity of water is related to the width of the base and the minimum of the two sides that make up the container
  • Suppose the capacity is Max; The container consists of endpoints (x1,y1) and (x2,y2); Has the Max = | x1 – x2 | * min (y1, y2)
  • Analysis, because | x1 – x2 | maximum value for the length of the array, the minimum value of 0; We can assume that we have a pointer to x1,x2
  • X1,x2, how do I find the movement of the pointer?
  • Start on this needs from y1, y2, because Max = | x1 – x2 | * min (y1, y2); Want so the Max becomes larger, the | x1 – x2 | set to smaller cases, min (y1, y2) as far as possible
  • How do I make min of y1,y2? Move y1,y2 to the next place;
  • Get the answer

code

var maxArea = function (height) {
  const len = height.length
  let left = 0
  let right = len - 1
  let result = 0
  while (left < right) {
    const total = (right - left) * Math.min(height[left], height[right])
    if (height[left] >= height[right]) {
      right--
    } else {
      left++
    }
    result = Math.max(total, result)
  }

  return result
}
Copy the code