【LeetCode】盛最多水的容器（python）

题目描述：

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

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

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解题思路：
思路一：
使用两个for循环对height数组进行遍历，不断迭代找到最大的面积，如下所示：
i为for循环所在位置，j为i之后的值，利用公式：min(height[i], height[j]) * (j - i)即可求得面积

		max_area = 0
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                temp = min(height[i], height[j]) * (j - i)
                if temp > max_area:
                    max_area = temp
        return max_area

结果： 上述解题思路的时间复杂度为O(nlogn)，在输入的数据量大时回超出运行时间限制：

思路二：
使用两个值i和j分别指向数组的头部和尾部，然后利用公式：min(height[i], height[j]) * (j - i)计算面积值，并根据height[i]和height[j]的值不断更新i和j所在位置，即若height[i]>height[j]，则j–，反之， i++

		i = 0 
        j = len(height) - 1
        max_value = 0
        while i != j:
            temp =  min(height[i], height[j]) * (j - i)
            if temp > max_value:
                max_value = temp
            if height[i] > height[j]:
                j -= 1
            else:
                i += 1
        return max_value

结果： 上述解题思路的时间复杂度为O(n)，在数据量大时也没有超出运行时间限制：

完整代码：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        '''
        方法一：
        max_area = 0
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                temp = min(height[i], height[j]) * (j - i)
                if temp > max_area:
                    max_area = temp
        return max_area
        '''
        
        '''
        方法二
        '''
        i = 0 
        j = len(height) - 1
        max_value = 0
        while i != j:
            temp =  min(height[i], height[j]) * (j - i)
            if temp > max_value:
                max_value = temp
            if height[i] > height[j]:
                j -= 1
            else:
                i += 1
        return max_value