• 分类：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

这个题要用动态规划思路，我觉得我还应该再强化一下。