11. Container With Most Water 盛最多水的容器

原题链接：https://leetcode.com/problems/container-with-most-water/
找出在n条垂直于x轴的线中能够组成的最大容器面积的两条线，容器不能倾斜，n的最小值为2.

解题思路：
1.暴力破解
设起始点为i，终点为j，找到能使面积最大的i和j。

classSolution:defmaxArea(self,height:List[int])->int:max_area=0foriinrange(len(height)):forjinrange(len(height)-1,i,-1):cur_area=min(height[i],height[j])*(j-i)ifcur_area>max_area:max_area=cur_areareturnmax_area

测试的时候发现这个方法虽然可行但是超时了…试图用动态规划来解决，但是好像也不是很可行, 运行的时候栈溢出了。最后看了答案，感觉答案里给出的这个思路还是有点难想到的。

设置两个指针i和j，分别代表第一条线和最后一条线。比暴力搜索优化的地方在于，当计算完当前面积的时候，比较一下i和j的大小，如果i > j, i = i + 1，如果i < j 的话，j = j -1。
这样做的原因是，每次i或者j向内移动， j - i都会随之变小，面积也会变小，所以需要保留相对高的高度来抵消j - i的变小

然后自己按照答案的思路实现了一下：

classSolution:defmaxArea(self,height:List[int])->int:max_area=i=0j=len(height)-1whilei<j:cur_area=min(height[i],height[j])*(j-i)ifcur_area>max_area:max_area=cur_areaifheight[i]<height[j]:i+=1else:j-=1returnmax_area

有一个意外的发现：在python里用max函数比写if else的条件语句还要慢···