题目

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

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

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

示例：

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

 分析

这个题如果用暴力解法，每个情况都计算一遍的话，会超时的。

我们可以从两端向中间逼近，定义begin和end两个指针，begin指向最左边，end指向最右边，begin从左向右走，end从右向左走，雨水量也比较容易计算，底乘高，底就是end-begin，高就是begin和end所在垂直线的比较短的那个高度。那么现在开始：

1. begin向左走，begin++，同时也要记录每次位置的雨水量，更新最大的雨水量，当遇到begin的垂直线高于end的垂直线，停止；

2. end开始向右走，end--，同时更新最大雨水量，当遇到end的垂直线高于begin的垂直线，停止；

3. 重复 步骤1 2 ，直到begin>=end, 我们就得到最终的结果啦。

代码

class Solution {
    public int maxArea(int[] height) {
        int begin = 0;
        int end = height.length-1;
        int result = 0;

        if (end-begin == 1) return Math.min(height[begin],height[end]);

        while (begin < end){
            while (begin < end && height[begin] <= height[end]){
                result = Math.max(result,height[begin] * (end-begin));
                begin ++;
            }
            while (end > begin && height[end] < height[begin]){
                result = Math.max(result,height[end] * (end-begin));
                end --;
            }
        }

        return result;
    }
}