每日一道 LeetCode (51)：盛最多水的容器
共 1004字，需浏览 3分钟
· 2020-09-25
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：盛最多水的容器
难度：「中等」
题目来源：https://leetcode-cn.com/problems/container-with-most-water/
给你 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
解题思路
今天这道题蛮有意思的，给出一个数组，实际上是在求这个数组之间可以组成的最大面积。
这道题正统的解法是使用双指针，因为是在数组之间灌水，能容纳的水有多少是取决于那个最小的数字，所以我们先把两个指针分别指向数组的头和尾，先求一下当前的面积，然后比较下头尾的大小，每次移动较小的那个指针，把整个数组迭代一遍，取出其中的最大值即可。
public int maxArea(int[] height) {
int len = height.length;
int start = 0, end = len - 1;
int maxArea = 0;
while (start != end) {
int area = Math.min(height[start], height[end]) * (end - start);
maxArea = Math.max(area, maxArea);
if (height[start] < height[end]) {
start++;
} else {
end--;
}
}
return maxArea;
}
代码看起来不难，声明一点哈，上面这个方案不是我想出来的，是看了答案的提示以后才知道的。
但是这里面有个问题，为什么这种方案是可以找到最大的面积的，难道就不会存在其他的情况么？
下面的这个证明方案同样来自于答案当中，用来证明上面这个方案的正确性。
双指针代表的是可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界，表示数组中所有的位置都可以作为容器的边界，因为我们还没有进行过任何尝试。
在这之后，我们每次将对应的数字较小的那个指针往另一个指针 方向移动一个位置，就表示我们认为这个指针不可能再作为容器的边界了。
那么为啥这个指针不能在作为容器的边界了，下面是这个问题的证明：
首先考虑第一步，假设当前左指针和右指针指向的数分别为 x 和 y，先假设 x < y ，同时两个指针之间的距离为 t ，那么他们组成的容器的容量为：
min(x, y) * t = x * t
这时可以断定，如果我们保持左指针的位置不变，那么无论右指针在哪里，这个容器的容量都不会超过 x * t 了。注意这里右指针只能向左移动，因为我们考虑的是第一步，也就是指针还指向数组的左右边界的时候。
我们任意的移动右指针，指向的数字为 y1 ，两个指针之间的距离为 t1 ，那么显然有 t1 < t ，并且 min(x, y1) <= min(x, y) 。
如果 y1 <= y 那么有 min(x, y1) <= min(x, y)。如果 y1 > y 那么有 min(x, y1) = x <= min(x, y)。
因此刚才上面的那个公式可推导：
min(x, y1) * t1 = min(x, y) * t
即无论我们怎么移动右指针，得到的容器的容量都小于移动前容器的容量。也就是说，这个左指针对应的数不会作为容器的边界了，那么我们就可以丢弃这个位置，将左指针向右移动一个位置，此时新的左指针于原先的右指针之间的左右位置，才可能会作为容器的边界。
这样以来，我们将问题的规模减小了 11，被我们丢弃的那个位置就相当于消失了。此时的左右指针，就指向了一个新的、规模减少了的问题的数组的左右边界，接下来，我们可以重复上面的这个过程，接着缩小容器边界。
