欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-14 14:13:15
...

https://leetcode-cn.com/problems/container-with-most-water/
11. 盛最多水的容器 双指针
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)该移动哪一个指针?:左挡板 小于等于 右挡板,那么就移动左指针。

相关标签: 算法题目