Question 1: the container that holds the most water

1. subject ： Container for the most water

 Here you are.  n  Nonnegative integers  a1,a2,...,an, Each number represents a point in the coordinate  (i, ai) . Draw in coordinates  n  Bar vertical line , vertical 
 Line  i  The two endpoints of are  (i, ai)  and  (i, 0) . Find two of them , Make them  x  A container composed of shafts can hold the most 
 More water .

 explain ： You can't tilt the container .

2. answer ： Violence law

Fixed starting point , Traverse every possible destination , Calculate the maximum area .

Cyclomatic complexity ：n^2

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxArea = 0

        for i, x in enumerate(height):
            k = 0
            area = 0
            for y in height[i + 1::]:
                k += 1
                area = max(area, k * min(x, y))
            maxArea = max(maxArea, area)
        
        return maxArea

Execution timeout , Through use cases ：49/60

image.png

3. Optimize ： Double finger needling

Find the maximum width first , That is, the two pointers point to the beginning and end of the container respectively ;

Then find the pointer to move to the middle , At this time, the width will decrease no matter moving the left or right 1, You must keep the higher points to get a larger area （ Move the lower point out ）, Update the maximum area with the current width and height

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 1
        right = len(height)
        maxArea = 0

        while right > left:
            if height[left - 1] < height[right - 1]:
                area = (right - left) * height[left - 1]
                left += 1
            else:
                area = (right - left) * height[right - 1]
                right -= 1
            maxArea = max(maxArea, area)
        
        return maxArea

image.png