欢迎来到军工软件开发人才培养基地——学到牛牛

力扣题库. 盛最多水的容器

时间:2024-05-06 07:01:10 来源:学到牛牛

题目描述:给定一个长度为 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。

 

题解思路:

1:使用两个指针,indexLeft和indexRight

2:面积的计算公式Are = high * wide,面积等于高 * 宽

3:计算high = fmin(height[indexRight] , height[indexLeft])

4: 计算wide = indexRight - indexLeft

5:计算出对应的Are与maxAre进行比较并更新maxAre

6: 移动indexRight 与 indexLeft中小的指针

 

当然也可以使用暴力法,把每个可能性都列举一遍找出最大值并返回,这种是对于大家来说最简单也是最好理解的方法

 

完整代码:

int maxArea(int* height, int heightSize)

{

    //暴力法  

    int indexLeft  = 0;  //  左边

    int indexRight = heightSize-1;   // 右边

    int Are = 0;   // 临时存储面积的变量

    int maxAre  = 0;  //  最大面积

    int h    = 0;  // 高

    int moveLeft = 0;

    while(indexLeft < indexRight)

    {

        //取短的一边

        if(height[indexLeft]<=  height[indexRight])

        {

            h = height[indexLeft];

            moveLeft = 1;

        }

        else

        {

            h = height[indexRight];

            moveLeft = 0;

        }

        Are = h *(indexRight - indexLeft);  //  求面积大小

        if(maxAre < Are)  // 每一次面积比较大小 找到最大值

        {

            maxAre = Are;

        }

        if(moveLeft)

{

            indexLeft++;

        }

else

{

            indexRight--;

        }

    }

    return maxAre;

}