LeetCode-第五期：11. 盛最多水的容器-20190301

LeetCode-第五期：11. 盛最多水的容器

#Datawhale代码打卡

题目描述

给定 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

思考

1. 确定最终输出 ，返回值是一个装水的面积值，由坐标差*min（高度值）得来的最大值；
2. 确定函数功能 ，计算装水的面积值，两个for循环便利指标i，j，Area=横坐标纵坐标=（j-i） * min（Height[j]，Height[i]）；计算后把每次Area的具体数值记录到Area这个list中，然后对Area这个list进行reshape（n*n）操作，最后对Area这个list进行max操作得到输出，同时也可以根据需要反馈最大装水面积对应的坐标值；
3. 确定函数输入 ，Height这个数组，自带从0开始的顺序位置和对应的高度信息。
4. 中间数据处理可能使用那些数据结构（类型） list的取值从0开始，累计在Area中需要用到append，reshape函数重新调整list的维度。

Round1

代码如下：
class Solution:
def maxArea(self, height: List[int]) -> int:
for i in range(nums(height)):
for j in range(nums(height)):
Area.append((j-i)*min(height[j]，height[i]))
return max(Area)

报错如下：
编译出错
Line 6: SyntaxError: invalid character in identifier

无效的定义，感觉应该是min(height[j]，height[i])取小值的操作导致了代码出错。
猜测因为缺少numpy库，更改语句为
Area.append((j-i)*numpy.min(height[j]，height[i])) #依然报错。。。。。

Round2

暴力解法：

1. 因为题目要求不需要返回具体的坐标，可能是我想多了；
2. numpy是自带的，上次报错的原因是(height[j]，height[i])中间是中文逗号，说明python的报错看得少，下次注意；
3. Area，局部变量需要在使用之前进行定义；
4. 来自商科的分析，每次增加或者减少的边际效用的毛病，先尝试暴力法解题吧，小规模的计算一般没啥问题，希望以后再参加训练营的时候可以注意。
   class Solution:
   def maxArea(self, height: List[int]) -> int:
   Area = 0
   for i in range(len(height)):
   for j in range(i,len(height)):
   Area=max(Area,(j-i)*min(height[j],height[i]))
   return Area

复杂度分析

1. 时间复杂度：O(n^2)[Round1]----->O(n(n-i)对于i=[1,n]的求和)，第一次尝试计算时间复杂度，感觉有点不太会；
2. 空间复杂度：O(n)O(n)O(n(n-i)对于i=[1,n]的求和)来自于(i,j,Area)，使用恒定的额外空间。

来源：http://www.icode9.com/content-4-127551.html