描述

给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水
1.你不能倾斜容器
2.当n小于2时，视为不能形成容器，请返回0
3.数据保证能容纳最多的水不会超过整形范围，即不会超过231-1

数据范围:
0<=height.length<=10^50<=height.length<=105
0<=height[i]<=10^40<=height[i]<=104

如输入的height为[1,7,3,2,4,5,8,2,7]，那么如下图:

示例1

输入： 
[1,7,3,2,4,5,8,2,7]
复制
返回值： 
49
复制

示例2

输入： 
[2,2]
复制
返回值： 
2
复制
解题思路：
1、很容易想到暴力解法，轮询height数组，依次计算每种可能性，然后再取最大面积值，但是会超时；
2、如何优化暴力解法呢？我们想想什么情况下面积可能最大？
1）两个数相距比较远；
2）两个数相对比较大；
3、将以上两个想法代码化：
相距比较远->首尾相距最远，但首尾可能高度比较小；可以用双指针分别指向首尾；
两个数相对比较大->分别比较两个指针指向的值，谁比较小就继续移动；
这个过程中计算每次遍历时的面积值与当前最大值之间取最大值。
这种通过局部最优解最终求得总体最优解的方式就是贪心算法。 


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型vector 
     * @return int整型
     */
    /*int maxArea(vector<int>& height) {
        // write code here
        int len = height.size();
        int res = 0;
        for (int i = 0; i < len - 1; i++){
            for (int j = i+1; j < len; j++){
                int tmp = (j - i)*(min(height[i], height[j]));
                res = max(res, tmp);
            }
        }
        return res;
    }*/
    int maxArea(vector<int>& height) {
        // write code here
        int len = height.size();
        int res = 0;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int tmp = (right - left) * (min(height[left], height[right]));
            res = max(res, tmp);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
};