算法 24 Container With Most Water

题目：给定n个非负整数a 1，a 2，...，a n，
在二维坐标系中，(i, ai) 表示 从 (i, 0) 到 (i, ai) 的一条线段，即数组中每个元素是一条这样的线段，在数组范围内任意两条这样的线段和 x 轴组成一个木桶，找出能够盛水最多的木桶，返回其容积。
注：不考虑倾斜

思路：常规思路，两层循环计算找出最大面积，会超时。
另一种解法
从两端开始向中间靠拢，如果左端线段短于右端，那么左端右移，反之右端左移，知道左右两端移到中间重合，记录这个过程中每一次组成木桶的容积，返回其中最大的。

当左端线段L小于右端线段R时，我们把L右移，这时舍弃的是L与右端其他线段（R-1, R-2, ...）组成的木桶，这些木桶是没必要判断的，因为这些木桶的容积肯定都没有L和R组成的木桶容积大。

代码：

public class Solution {
    public int maxArea(int[] height) {
        if (height.length < 2) return 0;
        int ans = 0;
        int l = 0;
        int r = height.length - 1;
        while (l < r) {
            int v = (r - l) * Math.min(height[l], height[r]);
            if (v > ans) ans = v;
            if (height[l] < height[r]) l++;
            else r--;
        }
        return ans;
    }
}

时间复杂度O(n),空间O(n)