hot100_盛最多水的容器

分析

题目说要盛最多的水，其实就是求最大的面积，长是两高之间的间隔，高是两高之间较低高。

题解

双指针

我们可以定义两个指针：

• left = 0：指针指向最开始的高
• right = height.size() – 1：指针指向最末尾的高

那么要什么移动呢？

设当前左右边界为

l

l

l、

r

r

r，

h

[

l

]

<

h

[

r

]

h[l] < h[r]

h[l]<h[r]：

当前面积

S

=

(

r

−

l

)

h

[

l

]

S = (r – l)h[l]

S=(r−l)h[l]

无论

r

r

r向左如何移动，宽度

(

r

′

−

l

)

<

(

r

−

l

)

(r'-l) < (r-l)

(r′−l)<(r−l)，且水位高度最大只能是

h

[

l

]

h[l]

h[l]，因此后续

l

l

l为左边界的所有情况，面积都不可能超过当前

S

S

S。

于是可以安全抛弃左指针

l

l

l，left++。

另一侧同理。

代码

class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() – 1;
int res = 0;
int area = 0;
while(left < right) {
if(height[left] < height[right]) {
area = (right – left) * height[left];
left++;
} else {
area = (right – left) * height[right];
right—;
}
res = max(res, area);
}
return res;
}
};

精简版代码

class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() – 1, ans = 0;
while (l < r) {
int h = min(height[l], height[r]);
ans = max(ans, (r – l) * h);
height[l] < height[r] ? l++ : r—;
}
return ans;
}
};

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

11. 盛最多水的容器 – 力扣（LeetCode）