LeetCode05：盛最多水的容器

5. 盛最多水的容器

题目

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

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

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

说明：你不能倾斜容器。

示例 1：

img

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

示例 2：

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

题解

（一）双指针

这道题的关键是需要理解装的水容量取决于：1、木板之间的距离、2、短木板的高度。

如图，Left指针和Right指针分别指向起点和终端：

image-20240329190613762

为什么是移动短板：

因为随着底部距离的减小，如果移动长板，新板高度大于/小于/等于短板，而容量取决于底部距离 * 短板高度，最终容量只会相等或更小。

移动短板，直至两个指针相遇，每次计算水的容量，最后取最大容量。

时间复杂度：O(n)，双指针总计最多遍历整个数组一次。

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxArea(self, height):
        length = len(height)
        area = 0
        i = 0
        j = length - 1
        while i < j:
            x = j - i
            y = min(height[i],height[j])
            area = max(area,x * y)
            if height[i] <= height[j]:
                 i += 1
            else:
                j -= 1
        return area

（二）暴力破解

双层for循环遍历。

缺点：非常耗时

时间复杂度：O($n^2$) n是数组的长度

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxArea(self, height):
        length = len(height)
        max_area = 0
        for i in range(length):
            for j in range(i+1,length):
                x = j - i
                y = min(height[i],height[j])
                area = x * y
                max_area = max(max_area,area)
        return max_area