11. 盛最多水的容器（中）

• 题目
• 法一、双指针暴力
• 法二、双指针的优化

题目

• 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

  找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

  返回容器可以储存的最大水量。

  说明：你不能倾斜容器。

法一、双指针暴力

• 用两个指针把所有可能的盛水容器遍历一遍，其中比较更新最大的盛水容器。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        if height is None:  # 如果输入的 height 为 None，返回 0
            return 0
        catchmax = 0  # 初始化保存最大盛水量的变量为 0
        for left in range(len(height)):  # 遍历左指针
            for right in range(left+1, len(height)):  # 遍历右指针，保证右指针在左指针的右侧
                # 计算当前容器的盛水量，取较小高度乘以两指针之间的距离
                catchmax = max(catchmax, (right - left) * min(height[left], height[right]))
        return catchmax  # 返回最大的盛水量

• 超时

法二、双指针的优化

class Solution:
    def maxArea(self, height: List[int]) -> int:
        if height is None:  # 如果输入的 height 为 None，返回 0
            return 0
        catchmax = 0  # 初始化保存最大盛水量的变量为 0
        left = 0  # 左指针初始位置
        right = len(height) - 1  # 右指针初始位置

        while left < right:  # 当左指针小于右指针时进行循环
            # 计算当前容器的盛水量，取较小高度乘以两指针之间的距离
            catchmax = max(catchmax, (right - left) * min(height[left], height[right]))

            if height[left] < height[right]:  # 如果左指针的高度较小，则将左指针向右移动一位
                left += 1
            else:  # 如果右指针的高度较小或相等，则将右指针向左移动一位
                right -= 1

        return catchmax  # 返回最大的盛水量