题目
题目.png
题意是说有n个非负的整数，他们分别以（i,ai）组成了n个点，每个点和（i,0）组成了垂直于x轴的直线，选取其中的两条直线和X轴会组成一个凹槽，问凹槽能装多少水。这题其实是求两条直线和X轴能够形成的最大面积，宽是两个点之间X轴差的绝对值。高是两个点中Y轴值最小的值。返回形成最大面积的值。
如下图中的A点和H点（area=H*W=min(HA,HG)x(8-1)=1x7=7
分析
图示.png
假设我们有上图中图示的点，该如何找满足题意的两条垂线呢？最简单的就是穷举所有的可能。任意选择其中的两条，求其中的最大值，但这样会有很多多余的不必要计算。我们的思想是从两边往中间移动来计算最大的面积。
我们先假设有两个索引点i和j,分别指向A点和H点。然后比较HA和HG，如果HA < HG则让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;
}
}
