盛最多水的容器

盛最多水的容器

问题描述

LeetCode 11. 盛最多水的容器
给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

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

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

说明：你不能倾斜容器。

解决思路

这个问题可以使用双指针方法来解决。我们可以定义两个指针 i 和 j，分别位于数组的起始和结束位置。然后，我们计算两个指针所指的垂线之间形成的容器的容积，并将其与当前最大容积进行比较。之后，我们将指向较短垂线的指针向内移动，因为移动较长垂线的指针不会增加容器的容积，而移动较短垂线的指针有可能增加容器的容积。

具体解决步骤如下：

1. 初始化指针 i 为 0，指针 j 为 n-1，其中 n 表示数组的长度。

2. 初始化最大容积 result 为 0。

3. 使用循环，计算当前指针 i 和 j 所指的垂线之间形成的容器的容积，并将其与当前最大容积 result 进行比较。

4. 将较短垂线的指针向内移动一步，即如果 height[i] < height[j]，则将指针 i 向右移动一步，否则将指针 j 向左移动一步。

5. 继续循环，直到指针 i 大于或等于指针 j 时停止。

6. 返回最大容积 result。

代码实现

以下是使用Python编写的代码，实现了上述解决思路，并添加了注释以解释每个步骤：

class Solution:
    def maxArea(self, height):
        if not height or len(height) <= 1:
            return 0

        i, j, result = 0, len(height) - 1, 0

        while i < j:
            if height[i] < height[j]:
                result = max(result, height[i] * (j - i))
                i += 1
            else:
                result = max(result, height[j] * (j - i))
                j -= 1

        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度分析

这个算法只需要遍历一次数组，因此时间复杂度是 O(n)，其中 n 是数组的长度。

空间复杂度分析

这个算法只使用了常数额外空间，因此空间复杂度是 O(1)。

结论

盛最多水的容器问题是一个经典的双指针问题，通过使用双指针方法，我们可以高效地找到容器可以容纳的最大水量。这个算法的时间复杂度和空间复杂度都在合理范围内，适用于大多数情况。希望这篇博客能够帮助你更好地理解和解决这个问题。