题目：给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线，使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
思路：双重循环，每次查找l—r区间内可以装的水的体积
注：要取左右两条线中较短的那条线的高度来作为容器的高
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
class Solution: def maxArea(self, height): """ :type height: List[int] :rtype: int """ contain_water = [] for l in range(len(height)-1): for r in range(l,len(height)-1): # 由l到r盛的水的容量 volumn = min(height[l],height[r])*(r-l) contain_water.append({'index':[l,r],'volumn':volumn}) max_contain = sorted(contain_water, key=lambda x: x['volumn'],reverse=True)[0]['index'] return max_contain a = [1,2,0,9,8] print(Solution().maxArea(a))
近期评论