11. 盛最多水的容器

问题

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

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

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

说明：你不能倾斜容器。

链接：11. 盛最多水的容器

题解

该问题要求，求x轴与左右边界所组成的最大面积，如下图：

我们记矩形左边界为left，右边界为right，则面积公式如下：

$Area = min(left_h,right_h)*(right_x - left_x - 1)$

那问题就是

1. 我们需要从哪里开始查找这个面积最大值
2. 如何查找呢？

对于第一个问题：我们需要从哪里开始查找这个面积最大值？

双指针代表的是 可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界，表示数组中所有的位置都可以作为容器的边界，因为我们还没有进行过任何尝试。在这之后，我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置，就表示我们认为 这个指针不可能再作为容器的边界了。

为什么对应的数字较小的那个指针不可能再作为容器的边界了？

考虑第一步，假设当前左指针和右指针指向的数分别为 $x$ 和 $y$，不失一般性，我们假设 $x≤y$。同时，两个指针之间的距离为 $t$。那么，它们组成的容器的容量为：

$min(x,y)t = xt$

我们可以断定，如果我们保持左指针的位置不变，那么无论右指针在哪里，这个容器的容量都不会超过 $x * t$ 了。注意这里右指针只能向左移动，因为 我们考虑的是第一步，也就是 指针还指向数组的左右边界的时候。

我们任意向左移动右指针，指向的数为 $y_1$，两个指针之间的距离为 $t1$, ，那么显然有$t1 < t$ ,并且 $min⁡(x,y_1)≤min⁡(x,y)$

1. 如果 $y1≤y$，那么 $min⁡(x,y1)≤min⁡(x,y)$
2. 如果 $y1＞y$，那么 $min⁡(x,y1)=min⁡(x,y)$

因此，无论我们怎么移动右指针，得到的容器的容量都小于移动前容器的容量。也就是说，这个左指针对应的数不会作为容器的边界了，那么我们就可以丢弃这个位置，将左指针向右移动一个位置，此时新的左指针于原先的右指针之间的左右位置，才可能会作为容器的边界。

作者：力扣官方题解 链接：https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

func maxArea(height []int) int {
	maxArea := 0
	left, right := 0, len(height)-1
	// 双指针遍历，直到指针汇聚
	for left < right {
		label := true
		// 找出最小的边作为矩形的高h
		if height[left] < height[right] {
			label = false
		}
		h := 0
		temp := 0
		// 根据最小边h的位置进行计算，如果是左边就left ++，右边就right --
		if label {
			h = height[right]
			temp = (right - left) * h
			right--
		} else {
			h = height[left]
			temp = (right - left) * h
			left++
		}
		if temp > maxArea {
			maxArea = temp
		}
	}
	return maxArea
}