11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i,height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

策略分析：

容器的容积决定于两个部分，一个是短板，一个是横向距离。

( j - i ) * min(height[i], height[j])

1. 采用暴力解法，依次遍历每两个竖线，计算他们的容积，取最大值。

for i in [0, length - 1]:
    for j in [i+1, length - 1]:
        temp = (j - i) * Math.min(nums[i], nums[j])
        if (temp > res):
            res = temp
return res

2. 双指针分析

假设我们选中第一条和最后一条线，它的容积是：size * Math.min(a[0], a[size])

 我们假设a[0] < a[size]，那么，a[0]与其他任意位置的线构成的容器的容积均不会超过这个值。

原因：

假如存在i, 0 < i < size, 使得Math.min(a[i], a[0]) * (i - 0) > size * Math.min(a[0], a[size])则要求

Math.min(a[i], a[0]) > Math.min(a[0], a[size])显然是不成立的。

因此，a[0] 和 a[size]在固定a[0]的时候，是最大的容器。变动右侧位置没有意义，只能提高短板才可能把容器提高。所以，左侧指针右移。

我们就得到了策略，移动值较小的那个指针，使得寻找一个比短板更大的值，得到更大容积的可能，直到两个指针相遇。

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = Integer.MIN_VALUE;
        while (left < right){
            int temp = 0;
            if (height[left] <= height[right]){
                temp = height[left] * (right - left);
                left++;
            } else {
                temp = height[right] * (right - left);
                right--;
            }
            if (temp > res){
                res = temp;
            }
        }

        return res;
    }
}