11. 盛最多水的容器

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

思路：

设立一个最大面积res

设一个左指针i一个右指针j，每次取左指针和右指针中小的值min(height[i],height[j])，乘以它们之间的坐标差(j-1)，算出来一个面积，如果比最大面积大，就更新最大面积，然后再比较height[i]和height[j]，如果height[i]比height[j]小，则i++，反之则j--，一直循环到i>=j为止

原理：

我们每次计算的都是的面积，若长是x，宽是y，则进行下一次计算时x会减1，即x会减少，为了获得更大的面积，我们需要更新短的那一根柱子，保有长的那一根柱子，这样才有几率获得更大的宽y，这样x*y才可能比最大的值大

代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ret=0;
        int temp;
        for(int i=0,j=height.size()-1;i<j;)
        {
            temp=min(height[i],height[j])*(j-i);      //计算2个指针的height围成的面积
            ret=ret>temp?ret:temp;                    //更新最大面积
            if(height[i]>height[j])                   //依据左右指针的height大小移动左右指针
                j--;
            else
                i++;
        }
        return ret;
    }
};

效率：

优化：

用一个keep存指针中小的那一个的height，判断更新后的指针的height是否比keep要大，如果不大，则继续更新直到大为止

代码：

static const auto __ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int maxArea(vector<int>& height) {
        int ret=0;
        int temp;
        int keep;
        for(int i=0,j=height.size()-1;i<j;)
        {
            temp=min(height[i],height[j])*(j-i);
            ret=ret>temp?ret:temp;
            if(height[i]>height[j])
            {
                keep=height[j];                        //不同的地方
                j--;
                while(height[j]<=keep)
                    j--;
            }
            else
            {
                keep=height[i];                        //不同的地方
                i++;
                while(height[i]<=keep)
                    i++;
            }
        }
        return ret;
    }
};

效率：