力扣题解8/10

11. 盛最多水的容器

难度中等3712

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

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

示例 2：

输入：height = [1,1]
输出：1

一，暴力法

由题目可以很容易联想到采用双循环来分别计算每个组合的面积，在保留其最大值

·面积的表达式为 fmin(a,b)*(b-a);但是使用暴力法会导致超时，因为其中包含着一些不必要的计算拖慢了代码执行的速度，所以我们要对其进行优化，那么如何减少不必要的计算呢？

 在这种情况下可以很清晰的看出当两侧的高度其中一侧足够低时，那么此时以这个高度和其他高度组合的情况下最大面积在最远处，而中间的情况是不必要计算的。然后我们将左指针向右移，在计算下种情况下的最大值

 这样，计算一类情况后将高度低的指针向中心移动就能在减少计算量的情况下得到最大面积

 采用了双指针来替代双重循环，具体代码如一下

int maxArea(int* height, int heightSize){
    int max=0,i=0,j=heightSize-1;
    while(i<j)
    {
        if(max<fmin(height[i],height[j])*(j-i))
            max=fmin(height[i],height[j])*(j-i);   
        if(height[i] < height[j])
            {
                i++;           
            }
            else
            {
                j--;            
            }       
    }        
    return max;
}