11. 盛最多水的容器

题目

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

说明：你不能倾斜容器。

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

自行解答：

本题目在题意读懂之后很容易想到O(n2)n平方的解法，很简单，双重for循环，直接遍历解答得到最后那个做大的容器体积，但是本题最大的难度其实不在此处，如果给出的数组较大，则双重for的时间复杂度会变得很高，直接超时，因此本题采用O(n)的解法，具体思路如下：

初始化首尾双指针
记录当前容器的体积大小，然后根据数据的大小移动指针指向的数值更小的指针，向内移动
重复2步骤，循环退出条件是首尾指针相等

ps：官方解答以及其他高赞回答都详细说明了下此种双指针为什么循环一次就能得到最大容器体积值，但是我觉得思路很清楚，即：

想要那个容器最大，其实很简单，保证长最大，宽(数组中某个位置上的值)最大即可，因此刚开始时长最大，指针移动的规则是题意要求，在长变小的过程中宽的大小最后决定了容器的大小，其中最大的那个就是满足题目要求的

关于会不会漏解：

从最长向最短的长边变化 && 移动规则(每次使用移动指针数值较短的指针)

2点规则决定不会漏解

int maxArea(vector<int>& height) {
   int maxWater = 0;
   int i = 0,j = height.size() -1 ;
   while(true){
     if(i == j){
     break;
     }
   int waterHeight = min(height[i],height[j]);
   int currentMaxWater = waterHeight * (j-i);
   if(currentMaxWater > maxWater){
       maxWater = currentMaxWater;
   }
   if(waterHeight == height[i]){
     i++;
   } else{
     j--;
   }
 }
 return maxWater;
}

复杂度分析：

时间复杂度：只循环一次因此O(n)的复杂度

空间复杂度：有限变量，因此O(1)