LeetCode 热题 100 11. 盛最多水的容器

LeetCode 热题 100 | 11. 盛最多水的容器

大家好，今天我们来解决一道经典的算法题——盛最多水的容器。这道题在LeetCode上被标记为中等难度，要求我们找到两条垂线，使得它们与 x 轴共同构成的容器可以容纳最多的水。下面我将详细讲解解题思路，并附上Python代码实现。

问题描述

给定一个长度为 n 的整数数组 height，其中 height[i] 表示第 i 条垂线的高度。你需要找到两条垂线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

注意：你不能倾斜容器。

示例：

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

解题思路

核心思想

1. 双指针法：

   • 使用两个指针 left 和 right，分别指向数组的起始和末尾。
   • 计算当前两个指针所指向的垂线构成的容器的面积，并记录下最大的面积。
   • 移动指针的规则是：移动指向较短垂线的指针，因为只有移动较短的垂线，才有可能在后续的步骤中找到更大的面积。

2. 面积计算：

   • 容器的面积由两个指针所指向的垂线中较短的那条决定，宽度为两个指针之间的距离。

Python代码实现

def maxArea(height):
    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

# 测试示例
print(maxArea([1,8,6,2,5,4,8,3,7]))  # 输出: 49
print(maxArea([1,1]))  # 输出: 1

代码解析

1. 初始化指针：

   • left 指向数组的起始位置，right 指向数组的末尾位置。

2. 计算面积：

   • 当前容器的面积由两个指针所指向的垂线中较短的那条决定，宽度为两个指针之间的距离。

3. 更新最大面积：

   • 每次计算完当前面积后，与之前的最大面积进行比较，更新最大面积。

4. 移动指针：

   • 根据当前两个指针所指向的垂线的高度，移动较短的垂线的指针，以期望在后续的步骤中找到更大的面积。

5. 返回结果：

   • 最终返回记录的最大面积。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组。
• 空间复杂度：O(1)，只使用了常数个额外空间。

示例运行

示例1

输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49

示例2

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

进阶：优化思路

在基本解法中，我们每次都会计算当前容器的面积并更新最大面积。如果数组中的垂线高度分布较为均匀，这种方法已经非常高效。但如果数组中有很多相同高度的垂线，可以进一步优化指针的移动策略，减少不必要的计算。

总结

通过使用双指针法，我们可以高效地找到能够容纳最多水的容器。这种方法不仅简洁，而且效率非常高，适合处理类似的问题。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！