Container With Most Water
你会得到一个由非负整数组成的列表 height。第 i 条线是一堵高度为 height[i] 的垂直墙，位于位置 i。任意两条线与地面都能形成一个容器，其盛水量等于较短那条线的高度乘以两条线之间的距离。其他线不会造成影响。返回一对线能够盛放的最大水量。
函数
- heightinteger-array
- 位置 0、1、2 等处的行高
- 返回值integer
- 两行最多能容纳的水量
约束条件
2 ≤ height.length ≤ 1040 ≤ height[i] ≤ 104- 答案最大为 108，因此可以用 32 位整数表示。
示例
- 输入
- height = [3, 7, 2, 5, 4, 7, 3, 6]
- 输出
- 36
- 解释
- 位置 1 和 7 处的线，高度分别为 7 和 6，相距 6，可以容纳 6 × 6 = 36。两条最高的线是位置 1 和 5 处高度为 7 的线，它们只能容纳 7 × 4 = 28。
- 输入
- height = [4, 4]
- 输出
- 4
- 解释
- 两条线恰好构成一个容器：高度为 4，宽度为 1，因此它能容纳 4。
进阶
这里会忽略两条线之间的线段。如果每条线都是一根实心柱子，它们之间总共能积多少水？你也能用 O(n) 时间计算出来吗？
提示
逐个打开提示，每个都会多透露一点。
先从两条最外侧的线开始：它们围成的容器最宽。将任一端向内移动都会损失 1 个单位的宽度。两条线中，哪一条有可能弥补这一点？
水的高度由较短的线限制。将较高的线向内移动会保留这个高度限制，却减少宽度，所以不可能有帮助。只有移动较短的线才有可能改善结果。
在两端各放一个指针。计算它们之间的水量，并记录最大值，然后将指向较短线段的指针向内移动一步。两个指针相遇时停止。
题解
检查所有 n²/2 对，需要计算 10^4 条线时的 5 × 10^7 个乘积。水量只取决于一对线中较短的那条。因此，一旦某条线成为它所能形成的最大容器的较短边，使用它的任何更窄容器都不可能装下更多水。双指针可以从两端同时开始，只遍历一遍。
检查每一对
结果正确，但无法在最大的测试中运行完毕
思路
一对 i < j 的面积为 min(height[i], height[j]) × (j - i)：水会从较短的墙溢出，底面宽度为 j - i。尝试每一对，并保留最大的面积。
n 条线会产生 n(n-1)/2 对：对于 10^4 条线，大约有 5 × 10^7 对；每当 n 翻倍，对数就会变成原来的 4 倍。
算法
- 将
best设为 0。 - 对于每个
i，以及它后面的每个j，计算min(height[i], height[j]) × (j - i)。 - 保留
best和该值中较大的那个。 - 返回
best。
def maxArea(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
water = min(height[i], height[j]) * (j - i)
best = max(best, water)
return best先显示最高的行
思路
如果第 i 条线是容器较短的一边，那么与它配对的线可以是任何至少一样高的线。因此，最佳容器会让它与距离最远的、至少一样高的线配对。
将这些线按从高到矮的顺序排列。当轮到第 i 条线时，所有已放置的线都至少和它一样高，其中距离最远的一条线是已放置索引中最左侧或最右侧的那条，即 lo 或 hi。因此，第 i 条线最多能形成面积为 height[i] × max(i - lo, hi - i) 的容器，而当较短的一边出现时，就会计入最佳容器。两条线高度相同时，后放置的那条会把先放置的那条视为配对线。
在第一个示例中，位置 1 和 5 的两条高度为 7 的线先出现，形成面积为 28 的容器。接着，位置 7 处高度为 6 的线会看到 lo = 1，并形成面积为 36 的容器。排序需要 O(n log n) 时间和 O(n) 内存。
算法
- 按高度对索引排序，从高到低排列。
- 将
lo和hi设为该顺序中的第一个索引，并将best设为 0。 - 对于后续的每个索引
i，计算height[i]乘以i - lo和hi - i中较大的值，并保留最佳值。 - 更新
lo和hi，使其包含i。 - 返回
best。
def maxArea(height):
# Indices from the tallest line to the shortest.
order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
lo = hi = order[0] # leftmost and rightmost index among the lines placed so far
best = 0
for i in order[1:]:
# Every placed line is at least as tall as line i, so line i is the
# shorter side, and its best partner is the placed line farthest away.
best = max(best, height[i] * max(i - lo, hi - i))
lo = min(lo, i)
hi = max(hi, i)
return best从两端开始的双指针
思路
从最宽的容器开始，令 left = 0、right = n-1，并假设 height[left] ≤ height[right]。其他所有使用 left 这条线的容器，都会与一条距离更近的线配对，因此宽度更小，高度也不会超过 height[left]。它们都无法盛下比你测量的水更多，所以 left 这条线可以排除，left 向右移动一步。两条线高度相等时，它们都可以排除，因此移动任意一条都可以。
每一步都会排除一条线，所以经过 n-1 步后，两个指针会相遇。最佳配对绝不会被跳过：当它的两条线中有一条先被移除时，那一刻测量的容器所盛的水至少一样多。
在第一个示例中，位置 0 和 7 盛有 21，移除高度为 3 的线。位置 1 和 7 盛有 36，移除高度为 6 的线。其余容器盛有 15、28、12、10 和 2。
算法
- 将
left = 0、right = n-1和best = 0设为初始值。 - 当
left < right时，计算min(height[left], height[right]) × (right - left)，并保留最大值。 - 如果
height[left] < height[right]，就将left向右移动一步。否则，将right向左移动一步。 - 当两个指针相遇时，返回
best。
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
best = max(best, water)
# The shorter line cannot do better with any line closer in, so drop it.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
易错点和边界情况
- 移动较高的线。在第一个示例中，结果是 21 而不是 36：位置 7 处的 6 还没遇到位置 1 处的 7，就已经离开了。
- 使用较高的线或两条线的平均值作为高度。水会从较矮的墙上溢出，因此高度取较小值。
- 将宽度计算为
j - i + 1。位置i和j处的线相距j - i，所以[4, 4]能装 4，而不是 8。 - 认为答案由最高的线或最外侧的一对线组成。在第一个示例中，两个 7 能装 28，最外侧的一对能装 21，而答案是 36。
常见问题3
盛水最多的容器的时间复杂度是多少？
双指针解法的时间复杂度为 O(n)，额外空间复杂度为 O(1)，因为每一步都会将一个指针向内移动一个位置。检查每一对需要 O(n²)，按高度对线条排序需要 O(n log n)。
为什么要把指针移到较短的那条线上？
水位受较短的线限制。任何保留这条线的其他容器，都有一条更靠内侧的线，因此容器更窄，也不会更高。它们都无法超过你测量的容器，所以可以舍弃较短的线，而不会影响答案。
盛水最多的容器是一道贪心问题吗？
是的。每一步都会做出一个不会撤销的局部选择：舍弃较短的边。这种选择是安全的，因为它排除的每个容器都不比已经测量过的容器更好，所以这个问题既属于贪心算法，也属于双指针。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def maxArea(height):
# 在这里编写代码测试 #1
测试 #2
参数
height = [3, 7, 2, 5, 4, 7, 3, 6]
预期输出
36