11. The container that holds the most water | brush and punch

create by db on 2021-3-11 16:10:51

Recently revised in 2021-3-11 16:22:59

Idle time to have a tight mind, busy time to have leisure fun

11. Containers that hold the most water > Contents

  • Topic describes
  • Thought analysis
  • AC code
  • conclusion

Topic describes

Returns the directory

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:

,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.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 <= 3 * 104
  • 0 <= height[i] <= 3 * 104

Thought analysis

Idea 1: Violent traversal

Try each combination of two bars one by one to work out the area and get the largest combination.

  • Time complexity: O(n^2), run n(n-1)/2 times
  • Space complexity: O(1), using only constant variables

tips:

Unfortunately, this algorithm has been ruled timeout by LeetCode…

Idea 2: Double pointer loop

Use a double pointer to move from both ends toward the center, moving the shorter end each time for other line segment attempts, still taking the maximum combination.

Just loop it once

  • Time complexity :O(n)
  • Space complexity :O(1)

AC code

Solution 1: Violent traversal

/ * * *@param {number[]} height
 * @return {number}* /
var maxArea = function (height) {
  if (height.length <= 1) {
    return 0
  }
  let maxArea = 0
  let area = 0
  let minBar = 0
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      minBar = Math.min(height[i], height[j])
      area = minBar * (j - i)
      maxArea = Math.max(maxArea, area)
    }
  }
  return maxArea
}
Copy the code

Solution 2: Double pointer loop

/ * * *@param {number[]} height
 * @return {number}* /
var maxArea = function (height) {
  let left = 0
  let right = height.length - 1
  let result = 0
  while (left < right) {
    result = Math.max(
      result,
      (right - left) * Math.min(height[left], height[right])
    )
    if (height[left] < height[right]) {
      left++
    } else {
      right--
    }
  }
  return result
}
Copy the code

conclusion

Returns the directory

March hello, spring flowers. Come on!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign

Postscript: Hello friends, if you think this article is good, remember to give a thumbs-up or star, your thumbs-up and star is my motivation to write more and richer articles!Making the address

Document agreement



dbThe document library 由 dbusingCreative Commons Attribution – Non-commercial Use – Same way Share 4.0 International LicenseGrant permission.

Based on thegithub.com/danygitgitOn the creation of works.

Use rights other than those authorized by this License agreement may be obtained fromCreativecommons.org/licenses/by…Obtained.