杰哥

V1

2022/12/06阅读:6主题:红绯

L-011 盛最多水的容器

L-011 盛最多水的容器

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

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

题解

本体采用双指针的思路,首先i,j固定于0和最后位置,每次判断两边那个是更低的高度,使用更低的高度乘以两个之间的距离用来更新容量。 更新完之后,将较短一边向内移动一步.

  • 假设i=0,j=8,此时i更短,如果更新j的话,下一步如果比j的值小,距离也变小则容量更小,如果比j大,则仍用i的高度,距离变小,容量还是小
  • **所以每次更新高度较小的值,以i为例,将i更新为i+1,会舍弃(i,i+1)...(i,j-1),这些都是比现有的容量小,因为不是距离小了就是高度变低 **
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i=0,j=height.size()-1,maxx=0;
        while(i<j){
            maxx=height[i]<height[j]?
            max(maxx,(j-i)*height[i++]):
            max(maxx,(j-i)*height[j--]);
        }
        return maxx;
    }
};

分类:

后端

标签:

C++

作者介绍

杰哥
V1