题目描述

[EN | CN]

给你 $n$ 个非负整数 $a_1$、$a_2$,...,$a_n$,每个数代表坐标中的一个点 $(i, a_i)$。在坐标内画 $n$ 条垂直线,垂直线 $i$ 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 $n$ 的值至少为 2。

LeetCode 11 Demo

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

示例:

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

解法 1:两指针往中间夹

最粗暴的方法就是遍历所有两边组合,我们思考应该如何优化。假如我们当前已经确定了两条边,算得了当前的面积,那么比这个面积更大的可能情况如下:

  • 两条边往外扩,宽度一定增加,高度可能增加或减少,最终面积不一定;
  • 两条边往中间缩,宽度一定减小,如果高度减少那么面积一定减小,如果高度增加那么可能面积增大。

那么我们有一个简单的思路,就是将两条边从数组的开头、结尾开始(假设为 lr),往中间夹:

  1. 计算当前的面积;
  2. 将短的边往中间缩小,直到遇到比短边更长的一条边,计算面积;
  3. 重复第二步直到 lr 相遇。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r, ret = 0, len(height) - 1, 0
        while l < r:
            ret = max(ret, (r - l) * min(height[l], height[r]))
            if height[l] < height[r]:
                tmp = height[l]
                l += 1
                while l < r and height[l] < tmp:
                    l += 1
            else:
                tmp = height[r]
                r -= 1
                while l < r and height[r] < tmp:
                    r -= 1
        return ret
  • 执行用时:56 ms,在所有 Python3 提交中击败了 96.95% 的用户。
  • 内存消耗:14.9 MB,在所有 Python3 提交中击败了 10.34% 的用户。