题目来源于LeetCode
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
题解:指针移动由最短边决定,无论长边移动后高度增加或者减少,都只能是装水量变少。
# 双指针
nums = [1, 8, 6, 2, 5, 4, 8, 3, 7]
left = 0
right = len(nums) - 1
maxContainer = 0
while left != right:
if nums[left] <= nums[right]:
maxContainer = max(maxContainer, (right - left) * nums[left])
left += 1
else:
maxContainer = max(maxContainer, (right - left) * nums[right])
right -= 1
print(maxContainer) # 49