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

说明：你不能倾斜容器，且 n 的值至少为 2。

image.png

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

示例：

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

解题思路

首先需要抽象出题目的数学模型，容器可以容纳的水也就是求矩形的面积，矩形的底可以通过数组下标来确定：j - i，高度由 最短的边决定，所以公式可以表示为：res = ( j - i ) * Math.min(height[j] , height[i]);

思路1：
暴力破解法，两层循环逐个遍历所有矩形，找出最大面积的矩形。
时间复杂度O(n*n),空间复杂度O(1)。

class Solution {

    public int maxArea(int[] height) {

        int max = Integer.MIN_VALUE;
        for(int i=0;i<height.length;i++)
        {
            for(int j=i+1;j<height.length;j++)
            {
                int val = (j-i) * Math.min(height[i],height[j]);
                max = Math.max(max,val);
            }
        }
        return max;
    }
}

运算结果：执行用时 :639 ms 内存消耗 :39.6 MB

思路2：
双指针，左右指针分别位于数组的始末位置，按照约定的规则移动指针直到两个指针重合，找到最大的矩形。

下面我们就要讨论下该如何移动指针：假设我们两个指针分别指向x和y，假设 x <= y ,间距为t，矩形的面积：min（x，y）* t
我们任意向左移动右指针到y1，两指针之间的间距t1，显然t1 < t 并且
如果y1 <= y ,那么 min(x , y1) <= min(x , y)
如果y1 > y ,那么 min(x , y1) = x = min(x , y)
我们有 ： min(x , y') * t' <= min(x,y)*t
所以不论怎么移动y，矩形的面积都不会大于之前的面积，也就是说移动较大的一边没有任何意义，我们每移动一次重新找到小的一边接着移动即可。

public int maxArea(int[] height) {

        int left = 0;
        int right = height.length-1;

        int max = 0;
        while(left < right)
        {
            if(height[left] <= height[right])
            {
                max = Math.max(max,(right-left) * height[left++]);
            }else
            {
                max = Math.max(max,(right-left) *height[right--]);
            }
        }

运算结果：执行用时 :3 ms 内存消耗 :39.4 MB

综上采用方法2.