题目

题目.png

题意是说有n个非负的整数，他们分别以（i,a_i）组成了n个点，每个点和（i,0）组成了垂直于x轴的直线，选取其中的两条直线和X轴会组成一个凹槽，问凹槽能装多少水。这题其实是求两条直线和X轴能够形成的最大面积，宽是两个点之间X轴差的绝对值。高是两个点中Y轴值最小的值。返回形成最大面积的值。

如下图中的A点和H点（area=H*W=min(H_A,H_G)x(8-1)=1x7=7

分析

图示.png

假设我们有上图中图示的点，该如何找满足题意的两条垂线呢？最简单的就是穷举所有的可能。任意选择其中的两条，求其中的最大值，但这样会有很多多余的不必要计算。我们的思想是从两边往中间移动来计算最大的面积。

我们先假设有两个索引点i和j,分别指向A点和H点。然后比较H_A和H_G，如果H_A < H_G则让i往右移，指向B点，反之则让j左移，指向G点。计算A和H形成的面积判断是否更新原来的面积。剩余的点同理计算，直到i和j发生交叉。

这样做能够减少大量计算。如图中的A和H两个点。我们知道A点的高＜H点的高，那么我们没有必要再去计算A点去其他点形成的最大面积，因为A和H形成的宽度是最大的（这是为什么从两端开始计算的原因，保证宽度最大），而A又是两点之间最矮的，就是说A点与除了H点的其他点形成的面积是肯定小于和H点形成的面积（宽度小于H和A的宽度，高度最多小于等于A的高度）。这样如果还有更大的面积形成，肯定是在除了A点以外剩余的点形成的，所以选择移动i，将其指向B（保证宽度最大），在余下的点中找最大的面积。按照类似的思想计算下去，就能找到最大的面积。

代码

代码是java版，以C语言写的话，应该会更快。

public class Solution 
{
    public int maxArea(int[] height) 
    {
        int arrSize=height.length;
        int max=0;
        int i=0;
        int j=arrSize-1;
        while(i<j)
        {
            int area=(j-i)*(height[i]<height[j]?height[i]:height[j]);
            max=area>max?area:max;
            if(height[i]<height[j])
            {
               i++;
            }
            else 
            {
                j--;
            }
        }   
        return max;
    }
}