算法喜刷刷

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

说明：你不能倾斜容器。

示例 1

输入：[1,8,6,2,5,4,8,3,7]

输出：49

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

容器的水量其实就是蓝色长方形的面积，也就是两条垂直线中最短的一条的高度和两条垂直线之间距离的乘积。

area(i,j)=min(height[i],height[j])*(j-i) (0<i<j)；

这里用动态规划的思想去实现。

一开始选取 y 轴和最右的边作为长方形的两条高，分别对应

height[i=0],height[j=array.length-1]

这时如果将 i 向右移动一个单位或者将 j 向左移动一个单位，我们可以发现长方形的长都是减少一个单位，所以不论 i 移动或者 j 移动对长的影响的一样的。

要想面积，那就必须使得高度增加，才能达到增加面积的效果，也就是说，在每次只能移动一个单位的规则，下一步，我们应该要去寻找高度高的垂直线来替换掉现有的那条矮的垂直线。

因此，如果是左边的垂直线高，就应该选择将右边的 j 向左移动，遍历出最高的垂直线；同理，如果是右边的垂直线高，就应该选择将左边的 i 向右移动，遍历出最高的垂直线。在这移动的过程中，寻找出最大的面积值，即为所求。