How to solve the problem of containers with the most Water in LeetCode

Editor to share with you how LeetCode solves the problem of containers with the most water. I hope you will get something after reading this article. Let's discuss it together.

one

Topic description

Given an array of n non-negative integers, where each number represents a point (I, ai) in the coordinates, do vertical lines with the x-axis respectively, and find out the two lines among them, so that the container composed of them and the x-axis can hold the most water and output area. As shown in the following figure, given an array of [3magentin 9pencils 3jorn 4pr 7pr 2je 12pr 6], in which the container composed of two green lines and x-axis can hold the most water, so the output is 45.

two

Answer to the question

Idea: the difficulty of this question is to think of double pointers and how to move them.

Double pointer: there are two lines involved in the topic, and there is a difference between left and right, so think of double pointer.

How to move the pointer: area = distance * shortest edge length. The maximum area is limited to two dimensions: the distance between two lines and the shortest line length. The farther the two lines are, the better, so first point the left and right pointer at both ends, so that the calculation starts from the longest distance; second, it is possible to increase the area by replacing the shortest of the two edges, so move the pointer at the smaller end.

Class Solution: def maxArea (self, height: List [int])-> int: I = 0j = len (height)-1 area = min (height [I], height [j]) * j while i=height [j]: J-= 1 else: I + = 1 if min (height [I] Height [j]) * (Jmuri) > area: area = min (height [I], height [j]) * (Jmuri) return area has finished reading this article I believe you have a certain understanding of "how LeetCode solves the problem of containers with the most water". If you want to know more about it, you are welcome to follow the industry information channel. Thank you for your reading!