11. 盛最多水的容器
一句话套路对撞指针,每次移动较矮的一侧
题目描述
给定一个长度为 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
提示:
n == height.length2 <= n <= 1050 <= height[i] <= 104
思路
时间
O(n)空间
O(1)思路
从最宽的两端开始。面积 = 宽 × min(高),宽度只会变小,所以想变大必须换掉「较矮的那根」——移动高的一端必然不更优。
反例
移动较高的一端,min 不会变大而宽度变小,面积必降。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 6
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0011 {
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = (int)height.size() - 1, ans = 0;
while (l < r) {
ans = max(ans, (r - l) * min(height[l], height[r]));
if (height[l] < height[r])
++l;
else
--r;
}
return ans;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0011::Solution s;
vector<int> a{1, 8, 6, 2, 5, 4, 8, 3, 7};
CHECK_EQ(s.maxArea(a), 49);
vector<int> b{1, 1};
CHECK_EQ(s.maxArea(b), 1);
vector<int> c{4, 3, 2, 1, 4};
CHECK_EQ(s.maxArea(c), 16);