Make writing a habit together! This is the 8th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details.

describe

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 20. Represented by array [1,8,6,2,5,4,8,3,7] the max area of water (blue section) the container can contain is 49.Copy the code

Note:

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
Copy the code

parsing

Given an integer array height of length n. N vertical lines are drawn such that the low and high points of the i-th line are (I, 0) and (I, height[I]) respectively.

Find two lines that, together with the X-axis, form a container that contains the most water. Returns the maximum amount of water a container can store.

Now, this is an interesting problem, because it’s very close to life, and we sometimes get this extreme under certain conditions. In fact, the topic examines both greedy algorithm and double pointer, and it is rare to combine the two knowledge points.

If it’s a violent solution, it’s going to time out, so you can use a double pointer to AC. We define S(I, j) as the accommodating area from I to J. Whether the leftmost column moves to the right or the leftmost column moves to the left, the width will become smaller. Therefore, to ensure the maximum capacity, we can only work on the height of the column, and there are two operations:

  • By removing the shorter column, so that the capacity of the container is determined by the shorter one, min(h[I], h[j]) * (j-i) may hold more water, and of course it may hold less water if it hits a shorter column
  • By removing the longer column, the capacity of the container is determined by the shorter one, so the shorter column min(h[I], H [j]) of the container will probably remain the same or be shorter, so the capacity will definitely be smaller

Therefore, we can use two Pointers to the left and right columns of the container. We remove the shorter pole in each round, update the maximum capacity until the two Pointers meet, and then return to the maximum area.

The time complexity is O(N), and the space complexity is O(N).

answer

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) == 2: return min(height[0], height[1]) * 1
        N = len(height)
        left = 0
        right = N - 1
        result =  min(height[left], height[right]) * (right - left)
        while left < right:
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
            result = max( result, min( height[right], height[left]) * (right-left) )
        return result		
Copy the code

The results

Given in the Python online submission to containers With Most Water. Submissions in the Python online submissions for containers With Most Water.Copy the code

The original link

Leetcode.com/problems/co…

Your support is my biggest motivation