11. 盛最多水的容器 双指针
程序员文章站
2022-07-14 14:13:15
...
https://leetcode-cn.com/problems/container-with-most-water/
python
class Solution:
def maxArea(self, height) -> int:
l, r = 0, len(height) - 1 # 左右指针
ans = 0
while l < r: # 左右指针指向同一个元素的时候退出循环
area = min(height[l], height[r]) * (r - l) # 面积 = 最短挡板 × 间距
ans = max(ans, area) # 答案只想要最大的面积
if height[l] <= height[r]: # 左挡板 小于 右挡板
l += 1 # 左指针移动
else:
r -= 1 # 右指针移动
return ans
print(Solution().maxArea([3, 5, 4]))
左右指针正确性:
(1)假设左指针指着height[0]不动;
(2)移动可行性:右指针指着height[-1],此时面积假设为area1。如果右指针移动,指着height[-2],此时面积假设为area2。间距的缩小,使得只有当height[-2]挡板大于之前的,才有可能找到更大的值。
(3)该移动哪一个指针?:左挡板 小于等于 右挡板,那么就移动左指针。