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.
Subscribe to see which companies asked this question.
有個(gè)高度數(shù)組栽连，就相當(dāng)于隔板的高度纳像，求數(shù)組中任意兩隔板間盛水的最大量。隔板間的距離與較低隔板的高度乘積即為盛水的容量。這個(gè)有點(diǎn)像是貪心法
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
size = len(height) # the size of height
maxm = 0 # record the most water
j = 0
k = size - 1
while j < k:
if height[j] <= height[k]:
maxm = max(maxm,height[j] * (k - j))
j += 1
else:
maxm = max(maxm,height[k] * (k - j))
k -= 1
return maxm
或者：
class Solution:
def maxArea(self, height: List[int]) -> int:
start, end, res = 0, len(height) -1 , 0
while start < end:
area = min(height[end], height[start]) * (end - start)
res = max(res, area)
if height[start] < height[end]:
start += 1
else:
end -= 1
return res
