Leetcode-盛水最多的容器(medium)

Problem description

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

Example

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

Solution

可将问题视为面积最大化问题，即将长和宽最大化

1. 首先将左右两边作为起始点，左点索引值为l,右点索引值为r，底边长度为r-l,此时
   底边长度为最大值

2. 当左边的值小于右边的值时，面积为左边的值乘以底边，并且左边索引往右移动一位，即l+1

反之，面积为右边的值乘以底边，并且右边索引往左移动一位，即r-1

3. 比较每次的面积area, if area > maxArea, 则maxArea = area

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxArea = 0
        length = len(height)-1
        l = 0 
        r = length
        for i in range(0,length):
            if height[l] > height[r]:
                area = height[r]*(r-l)
                r = r-1
            else:
                area = height[l]*(r-l)
                l = l+1
            if area > maxArea:
                maxArea = area
            
        return maxArea