,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。...找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。
?
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。...首先,本题自然可以暴力求解,只要找到每对可能出现的线段组合,然后找出这些情况下的最大面积。这种解法直接略过,大家有兴趣可以下去自己尝试。...首先,我们初始化两个指针,分别指向两边,构成我们的第一个矩形区域。
?
我们尝试将长的一侧向短的一侧移动,发现对于区域面积增加没有任何意义。比如下图:
?
所以我们选择将短的一侧向长的一侧移动。...根据木桶原理,水的高度取决于短的一侧。
?
继续重复这个过程,我们总是选择将短的一侧向长的一侧移动。并且在每一次的移动中,我们记录下来当前面积大小。