题目：
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
题意：
这道题的要求是给定整形数组a，(i, ai)表示坐标点，这些坐标点向x轴作垂直的线。找到两条线，使其和x轴共同构成的容器，可以装下最多的水。（注意，不允许倾斜容器）
每次做题都尽量先自己写，当看到acc时还是蛮开心的，然后看看别人写的程序，总是会有一种顿悟的感觉。
我本人的解题思路：
想到的最简单的方法是从左到右遍历一下给定的数组，利用两重循环O(n2)来实现，这样很明显会超时。接下来就想想什么地方可以优化一下：第一层循环从左到有遍历数组，第二层循环可以从右到左遍历一下，找到大于左边left的高度时就可以用break跳出本次循环了,因为容器的最大高度是被left限制了的，而此时高度达到了最大，且（j-i）是最大的，就找到了对于每个left的最大容积，写出代码后提交一下，发现最后一组测试数据超时了（还是可以有优化的地方），考虑了一下第二层循环已经优化了，那就看看第一层循环吧，在从左到右遍历的过程中如果当前left的height小于之前的某一个left的hright,那么就可以用continue跳过本次循环了，因为容器的最大高度比之前的要小，而且（j-i）也肯定小了，最大的容积肯定不会出现在当前的left。
优化之后的代码通过了测试，就去看了看别人的代码，发现自己从右到左优化了，从左到右优化了，就是没有想到利用两个指针，分别从左、右开始遍历(想想很衰）
先贴一下自己写的代码：
public class Solution {
public int maxArea(int[] height) {
int maxa = 0;
int maxi = 0; //存从左到右遍历过程中最高的left
if(height.length<2)
return 0;
for(int i=0;i<height.length-1;i++){
if(height[i]<height[maxi]){
continue;
}
for(int j=height.length-1;j>i;j--){
if(height[j]>height[i]){
int maxmid = (j-i)*height[i];
maxa = maxa>maxmid?maxa:maxmid;
break;
}
else{
int maxmid = (j-i)*height[j];
maxa = maxa>maxmid?maxa:maxmid;
}
}
maxi = i;
}
return maxa;
}
}
这里先说说利用两个指针从两边向中间遍历的大致思路：
先找距离最长的两个位置看能装下多少水，随后缩小两边的距离，因为距离减少，所以要想使得所能容纳的水变多，只能提高形成的“桶”的高度。因为高度与最低的边界一致，所以缩小边界时要从值小的那一边找，知道找到大于“桶高”的值，说明桶的高度可以得到提升，计算新桶所能容纳的体积并与最大值比较。以此类推，直到两边不能再缩小位置。
这种思路大致理解一下还是可以的，但是自己总是感觉有某种假设不能满足，也没办法很好的说明，就将自己理解过程中画的几种情况列出来
验证的过程就不多写了，感觉要写好多····
代码：
public class Solution {
public int maxArea(int[] height) {
int maxa = 0;
int i = 0,j=height.length-1;
while(i<j){
int maxmid;
if(height[i]<height[j]){
maxmid = (j-i)*height[i];
i++;
}
else{
maxmid = (j-i)*height[j];
j--;
}
maxa = maxa>maxmid?maxa:maxmid;
}
return maxa;
}
}
这里的代码还是可以由优化的地方的就是当前的left小于之前的left的时候就不要求maxa了。