preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

I give you n non-negative integers A1, A2… Each number represents a point (I, ai) in the coordinates. N vertical lines are drawn in the coordinates. The two endpoints of vertical line I are (I, ai) and (I, 0). Find two of these lines so that they, together with the X-axis, can hold the most water in the container. Note: You cannot tilt a container.

Example 1:Input:,8,6,2,5,4,8,3,7 [1]

Output: 49

Explanation: the vertical lines represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum that the container can hold water (shown in blue) is 49.

Example 2: Input: height = [1,1] Output: 1

Example 3: input: height = [4,3,2,1,4] output: 16

Example 4: input: height = [1,2,1] output: 2

Link: leetcode-cn.com/problems/co…

Answer key

  1. A violent solution, starting at array 0, iterates through each element to form a container, calculates how much water can be held, and returns the maximum value. The time complexity of this method is O(n ^ 2), so I won’t go into that here.
  2. Double pointer method, the amount of water in the container is mainly determined by two factors, one is the width of the container, the other is the height of the container, corresponding to the array is the two elements of the subscript distance and the smaller value of the two elements. Then we define two Pointers, left and right, pointing to the leftmost and rightmost of the array, respectively. The width of the container formed is the widest among all the containers that can be formed, and the volume of the container is min(hight[left], Hight [right]) * (right-left), and the next step is to move left to right or right to left. Why is it moving like this? Because according to the principle of the bucket, the short element determines how much water the bucket can hold. When the element pointed to by left is small, the water that the left bucket can hold with this element will not exceed the water amount of the bucket formed by the current and right (at this time, the widest), excluding all cases in which the current left bucket is the left bucket, thus reducing The Times of traversal. The left and right Pointers then move in the same order until they meet, at which point the maximum volume is obtained.
/ * * *@param {number[]} height
 * @return {number}* /
var maxArea = function(height) {
    l = 0
    r = height.length - 1
    ans = 0
    while(l < r) {
        h = Math.min(height[l], height[r])
        ans = Math.max(ans, h * (r - l))
        if(height[l] < height[r]) {
            l++
        } else {
            r--
        }
    }
    return ans
};
Copy the code