11.盛水最多的容器 python

题目

题目描述

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

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

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

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

题目链接

盛水最多的容器

题解

要解决这个问题，可以使用双指针法。双指针法的基本思想是从数组的两端开始，逐渐向中间移动，每次移动较短的那条垂线，以期望找到更高的垂线来增加容器的高度。

算法步骤

1. 初始化指针：设置两个指针 left 和 right，分别指向数组的起始位置和结束位置。
2. 计算初始面积：计算当前两条垂线与 x 轴构成的容器的面积。
3. 移动指针：比较两条垂线的高度，移动较短的那条垂线，以期望找到更高的垂线。
4. 更新最大面积：在每次移动指针后，重新计算当前容器的面积，并更新最大面积。
5. 终止条件：当两条垂线相遇时，终止循环。

Python 实现

def maxArea(height: List[int]) -> int:
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        # 计算当前容器的面积
        current_area = min(height[left], height[right]) * (right - left)
        # 更新最大面积
        max_area = max(max_area, current_area)
        
        # 移动较短的那条垂线
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

详细解释

1. 初始化指针：

   • left 指向数组的起始位置 0。
   • right 指向数组的结束位置 len(height) - 1。
   • max_area 初始化为 0，用于记录最大面积。

2. 计算初始面积：

   • 当 left 和 right 指针不相遇时，计算当前两条垂线与 x 轴构成的容器的面积。
   • current_area = min(height[left], height[right]) * (right - left)：容器的面积取决于较短的那条垂线的高度和两条垂线之间的距离。

3. 移动指针：

   • 比较 height[left] 和 height[right]，移动较短的那条垂线。
   • 如果 height[left] < height[right]，则 left 向右移动一位。
   • 否则，right 向左移动一位。

4. 更新最大面积：

   • 每次移动指针后，重新计算当前容器的面积，并更新 max_area。

5. 终止条件：

   • 当 left 和 right 指针相遇时，终止循环，返回 max_area。

通过这种方法，我们可以在 O(n) 的时间复杂度内找到可以容纳最多水的容器。

提交结果