盛最多水的容器

1. 题目描述

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

2. 示例

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例2

输入：height = [1,1]
输出：1

示例3

输入：height = [4,3,2,1,4]
输出：16

示例4

输入：height = [1,2,1]
输出：2

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

3. 解题

设两点为$(i, a_i), (j, a_j), (j>i), (a_j>a_i)$, 则其容纳水量为$$S= (j-i)*min(a_i, a_j)$$

1. 很容易想到的方法是暴力法，挨个算出其盛水数量，取其中最大值。此种方法时间复杂度为O(n*n), 空间复杂度为O(1)，但此种方法超时

2. 双指针法 开始时左指针指向头i，右指针指向末尾j，若$i<j, a_i<a_j$，则其容纳水量为$(j-i)*min(a_i, a_j) = (j-i)*a_i$，此时若将j左移，则$S$必定减少，简单证明： 将j左移，

• 若$a_j$不变，则此时$S$为 $(j-1-i)*min(a_j, a_i) = (j-1-i)*a_i < (j-i)*a_i$，$S$减少
• 若$a_j$增加,则此时$S$为 $(j-1-i)*min(a_j, a_i) = (j-1-i)*a_i < (j-i)*a_i$，$S$减少
• 若$a_j$减少但仍大于$a_i$,则此时$S$为 $(j-1-i)*min(a_j, a_i) = (j-1-i)*a_i < (j-i)*a_i$，$S$减少，若$a_j$此时小于$a_i$，显然仍减少

无论$j$左移后$a_j$如何变化，最后所得$S$必定减少，即我们证明了当左边界为$i$时，无论右边界为多少（可以为数组中除$a_i$外的任何值），$S’$必然小于当前$S$，因此左边界为$i$的种种组合我们可以直接舍弃，也就是将$i$右移。

这样，经过一次次舍弃，即移动值较小的指针，并记录移动过程中得出的$S$最大值，当两指针重合时，即可得出结果