11. 盛最多水的容器双指针

https://leetcode-cn.com/problems/container-with-most-water/

在这里插入图片描述

python

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）该移动哪一个指针？：左挡板小于等于右挡板，那么就移动左指针。