分类：Array
考察知识点：Array(数组遍历) 动态规划
最优解时间复杂度：O(n)
11. Container With Most Water
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.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
这道题最优的解法就是动态规划，一方面找到那一条最长的轴，一方面遍历数组。
代码：
最优解法:
class Solution:
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
L,R,width,res=0,len(height)-1,len(height)-1,0
for w in range(width,0,-1):
if height[L]<height[R]:
res=max(res,height[L]*w)
L+=1
else:
res=max(res,height[R]*w)
R-=1
return res
讨论：
1.这个题目最傻的方法让人是两个for循环，这个不用说
2.这个题感觉还是用到了动态规划，一方面是去找它的那条最长轴，一方面算它的最大面积。
WechatIMG1580.jpeg
这个题要用动态规划思路，我觉得我还应该再强化一下。
