杰
杰哥
V1
2022/12/06阅读:7主题:红绯
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;
}
};
作者介绍
杰
杰哥
V1