需求
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
方法一：双指针法
- 2个坐标点之间的容器面积
=x轴之差*y轴之差； -
x轴对应的是数组中元素的索引，y轴对应的是数组中元素的值； - 面积表达式:
area = min(height[i], height[j]) * (j - i)，使用两个指针，值大的指针不动，值小的指针向内移动遍历，这样就减小了搜索空间； - 参考代码
def max_size(height):
n = 0
m = len(height) - 1
tmp = []
while n != m:
r = (m - n) * min(height[n], height[m])
tmp.append(r)
if height[n] < height[m]:
n += 1
else:
m -= 1
return max(tmp)
a = [1,8,6,2,5,4,8,3,7]
print(max_size(a))
49
方法二：排列组合
- 通过
itertools模块的函数combinations()对数组的索引，进行两两组合，即可同时获得索引组合和值组合，进而求出所有容器的面积； - 这种方法的效率较低，在LeetCode上提交时超时，不推荐；
- 参考代码
from itertools import combinations
def get_max_size(a):
r = []
for i in combinations(range(len(a)), 2):
j = (i[1] - i[0]) * min(a[i[0]], a[i[1]])
r.append(j)
return max(r)
a = [1,8,6,2,5,4,8,3,7]
print(get_max_size(a))
49
方法三：暴力法
- 迭代遍历数组，进行组合，求出所有容器的面积，再求最大值；
- 这种方法的效率较低，在LeetCode上提交时超时，不推荐；
- 参考代码
def max_size(height):
tmp = []
for i, j in enumerate(height):
for k, v in enumerate(height[i+1:]):
r = (k + 1) * min(j, v)
tmp.append(r)
return max(tmp)
a = [1,8,6,2,5,4,8,3,7]
print(max_size(a))
49
