题解 | #装最多水的容器#

思路1：
暴力解答。直接进行两重遍历，寻找面积最大值，计算面积的公式就是
abs(j-i)*min(height[i],height[j])
即，用i、j分别表示容器底的左右边界，二者差值表示底长，i和j对应高度中的较小值表示容器高度，而这乘积即为所求。

代码如下：

class Solution {
public:
    /**
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
        int i = 0;//数组下标
        int j = 0;//容器的底
        int maxV = 0;//记录面积的最大值
        int len = height.size();
        if(len<2)
        {
            return 0;
        }
        //复杂度为O(n^2)
        for(i=0;i<len;i++)
        {
            for(j=0;j<len;j++)
            {
                if(maxV < abs((j-i))*min(height[i],height[j]))
                {
                    maxV=abs((j-i))*min(height[i],height[j]);
                }
            }
        }
        return maxV;
    }
};

思路2：
第一种思路是相当于i，j都从头开始，那么当i在前一半，j在后一半的情况，和，i在后一半，j在前一半的情况，是重复的。于是可以从这个方面来进行优化。
定义两个下标，一个从头开始(left)，一个从尾开始(right)，对半查找。循环停止的条件就是二者相等，所以一个while循环就可以搞定，保证left<right。
接下来就要计算面积。right-left就是底长，这个很好理解；容器高度还是选择height[left]和height[right]中的较小值；关键在于两个下标如何移动。
假设下标为x和y的时候面积最大，那么当left移到x的时候，如果right > y,那么height[right]一定小于
height[x]和height[y]中的较小值，才能保证假设成立，所以
height[right] < height[x](也就是height[right] < height[left])
height[right] < height[y]
那么此时移动的就应该是right的这个下标，让他向y靠近。
同理right先移到y的情况分析也是像上面一样。
综上，对比height[right] 和 height[left]，哪个小就移动哪个下标，left右移进行++操作，right左移进行--操作。

代码如下：

class Solution {
public:
    /**
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
        int maxV = 0;//记录面积的最大值
        int len = height.size();
        if(len<2)
        {
            return 0;
        }
        //优化
        int left = 0;
        int right = len-1;
        while(left < right)
        {
            if(height[left] < height[right])
            {
                maxV=max(maxV,(right-left)*height[left]);
                left++;
            }
            else
            {
                maxV=max(maxV,(right-left)*height[right]);
                right--;
            } 
        }
        return maxV;
    }
};