給定一組長短不一的隔板,挑其中的兩塊板,使得板子之間能裝最多的水。
注意點:
兩塊板之間能裝多少水是由短的那塊板決定的 選定兩塊板之後,它們之間的板就不存在了例子:
輸入: height=[1,1,1]
輸出: 2
我們把兩塊板分為左板、右板,現在考慮如下情況。假設左板高度為h,且比右板低,兩塊板之間的距離為w,則此時最多能裝水w*h,此時我們嘗試移動隔板。如果將左板向右移,那麼有可能使容積變大,例如,左板右邊的板子高h1(還是比右板低),此時最多裝水(w-1)*h1,有可能比w*h大;如果將右板向左移,由於水的高度不能高於左板,所以容積最多為(w-1)*h,肯定比w*h小。基於上面的假設,我們只要把兩塊隔板依次向中間靠攏,就可以求出最大的容積。
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height:
return 0
left = 0
right = len(height) - 1
result = 0
while left < right:
if height[left] < height[right]:
area = height[left] * (right - left)
result = max(result, area)
left += 1
else:
area = height[right] * (right - left)
result = max(result, area)
right -= 1
return result
if __name__ == "__main__":
assert Solution().maxArea([1, 1]) == 1