011. 盛最多水的容器 | Leetcode题解
点击上方“蓝色字体”，选择“设为星标”
每天复习一道面试题，轻松拿大厂Offer~
题目描述
给你 n 个非负整数 a1，a2，...，a``n，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 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
示例 3：
输入：height = \[4,3,2,1,4\]
输出：16
示例 4：
输入：height = \[1,2,1\]
输出：2
提示：
n = height.length2 <= n <= 3 * 1040 <= height[i] <= 3 * 104
难度：
难度：中等 支持语言：JavaScript、Python、C++
相关标签
双指针
相关企业
字节 腾讯 百度 阿里
复杂度分析
时间复杂度：由于左右指针移动的次数加起来正好是 n， 因此时间复杂度为 。 空间复杂度：。
思路 1（javascript）:
题目中说找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 ，因此符合直觉的解法就是固定两个端点，计算可以承载的水量， 然后不断更新最大值，最后返回最大值即可。这种算法，需要两层循环，时间复杂度是 。
代码（JS）:
let max = 0;
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
const currentArea = Math.abs(i - j) * Math.min(height[i], height[j]);
if (currentArea > max) {
max = currentArea;
}
}
}
return max;
虽然解法效率不高，但是可以通过（JS 可以通过，Python 不可以，其他语言没有尝试）。那么有没有更优的解法呢？
我们来换个角度来思考这个问题，上述的解法是通过两两组合，这无疑是完备的。我们换个角度思考，是否可以:
先计算长度为 n 的面积 然后计算长度为 n-1 的面积 ... 计算长度为 1 的面积。
很显然这种解法也是完备的，但是似乎时间复杂度还是 , 不要着急，我们继续优化。
考虑一下，如果我们计算 n-1 长度的面积的时候，是可以直接排除一半的结果的。
如图：
比如我们计算 n 面积的时候，假如左侧的线段高度比右侧的高度低，那么我们通过左移右指针来将长度缩短为 n - 1 的做法是没有意义的，因为新形成的面积变成了(n-1) * heightOfLeft， 这个面积一定比刚才的长度为 n 的面积 （n * heightOfLeft） 小。
也就是说最大面积一定是当前的面积或者通过移动短的端点得到。
关键点解析
双指针优化时间复杂度
Js中文网 - 前端进阶资源教程 www.javascriptC.com,typescript 中文文档 Javascript中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js……等，以帮助开发者成长为愿景的社区
思路 2
这道题目看似简单，做起来才发现不容易。分治法、动态规划都用不上，要想得到 O(n)O(n) 的解法只有使用双指针一条路。即使看了答案知道了双指针解法，你也可能并不清楚这个解法为什么正确。为什么双指针往中间移动时，不会漏掉某些情况呢？
如果没有真正理解题目，即使一次对着答案做出来了，再次遇到这个题目，还是可能做不出来。要理解这道题的正确性和原理，需要从背后的缩减搜索空间的思想去考虑题解。下面我将用图片解释这道题的正确性和原理。
双指针解法的正确性
思路 3
算法流程： 设置双指针 iii,jjj 分别位于容器壁两端，根据规则移动指针（后续说明），并且更新面积最大值
res，直到i == j时返回res。指针移动规则与证明： 每次选定围成水槽两板高度 h[i]h[i]h[i],h[j]h[j]h[j] 中的短板，向中间收窄 111 格。以下证明：
设每一状态下水槽面积为 S(i,j)S(i, j)S(i,j),(0<=i<j<n)(0 <= i < j < n)(0<=i<j<n)，由于水槽的实际高度由两板中的短板决定，则可得面积公式 S(i,j)=min(h[i],h[j])×(j−i)S(i, j) = min(h[i], h[j]) × (j - i)S(i,j)=min(h[i],h[j])×(j−i)。
在每一个状态下，无论长板或短板收窄 111 格，都会导致水槽 底边宽度 −1-1−1：
若向内移动短板，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能变大，因此水槽面积 S(i,j)S(i, j)S(i,j) 可能增大。
若向内移动长板，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 不变或变小，下个水槽的面积一定小于当前水槽面积。
因此，向内收窄短板可以获取面积最大值。换个角度理解：
若不指定移动规则，所有移动出现的 S(i,j)S(i, j)S(i,j) 的状态数为 C(n,2)C(n, 2)C(n,2)，即暴力枚举出所有状态。
在状态 S(i,j)S(i, j)S(i,j) 下向内移动短板至 S(i+1,j)S(i + 1, j)S(i+1,j)（假设 h[i]<h[j]h[i] < h[j]h[i]<h[j] ），则相当于消去了 S(i,j−1),S(i,j−2),...,S(i,i+1){S(i, j - 1), S(i, j - 2), ... , S(i, i + 1)}S(i,j−1),S(i,j−2),...,S(i,i+1) 状态集合。而所有消去状态的面积一定 <=S(i,j)<= S(i, j)<=S(i,j)：
短板高度：相比 S(i,j)S(i, j)S(i,j) 相同或更短（<=h[i]<= h[i]<=h[i]）；
底边宽度：相比 S(i,j)S(i, j)S(i,j) 更短。
因此所有消去的状态的面积都 <S(i,j)< S(i, j)<S(i,j)。通俗的讲，我们每次向内移动短板，所有的消去状态都不会导致丢失面积最大值 。
代码
JavaScript 实现
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
if (!height || height.length <= 1) return 0;
let leftPos = 0;
let rightPos = height.length - 1;
let max = 0;
while (leftPos < rightPos) {
const currentArea =
Math.abs(leftPos - rightPos) *
Math.min(height[leftPos], height[rightPos]);
if (currentArea > max) {
max = currentArea;
}
// 更新小的
if (height[leftPos] < height[rightPos]) {
leftPos++;
} else {
// 如果相等就随便了
rightPos--;
}
}
return max;
};
/**
作者：li-zhui-zhui
链接：https://leetcode-cn.com/problems/container-with-most-water/solution/11-sheng-zui-duo-shui-de-rong-qi-by-li-zhui-zhui/
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let res = 0, i = 0, j = height.length - 1, cur = 0;
while (i < j) {
let h = height[i] < height[j] ? height[i] : height[j];
cur = h * (j - i);
res = cur > res ? cur : res;
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return res;
};
C++ 实现
class Solution {
public:
int maxArea(vector<int>& height) {
auto ret = 0ul, leftPos = 0ul, rightPos = height.size() - 1;
while( leftPos < rightPos)
{
ret = std::max(ret, std::min(height[leftPos], height[rightPos]) * (rightPos - leftPos));
if (height[leftPos] < height[rightPos]) ++leftPos;
else --rightPos;
}
return ret;
}
};
/*
作者：nettee
链接：https://leetcode-cn.com/problems/container-with-most-water/solution/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu/
*/
int maxArea(vector<int>& height) {
int res = 0;
int i = 0;
int j = height.size() - 1;
while (i < j) {
int area = (j - i) * min(height[i], height[j]);
res = max(res, area);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return res;
}
Python 实现
class Solution:
def maxArea(self, heights):
l, r = 0, len(heights) - 1
ans = 0
while l < r:
ans = max(ans, (r - l) * min(heights[l], heights[r]))
if heights[r] > heights[l]:
l += 1
else:
r -= 1
return ans
# 作者：jyd
# 链接：https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
class Solution:
def maxArea(self, height: List[int]) -> int:
i, j, res = 0, len(height) - 1, 0
while i < j:
if height[i] < height[j]:
res = max(res, height[i] * (j - i))
i += 1
else:
res = max(res, height[j] * (j - i))
j -= 1
return res
# 作者：lxj618
# 链接：https://leetcode-cn.com/problems/container-with-most-water/solution/shuang-zhi-zhen-bian-li-by-lxj618/
class Solution:
def maxArea(self, height: List[int]) -> int:
# 长度不断缩短，缩短的过程中只缩短值小的一边
ans = 0
idx_1, idx_2 = 0, len(height)-1
while idx_1 < idx_2:
ans = max(ans, (idx_2-idx_1)*min(height[idx_1],height[idx_2]))
if height[idx_1] < height[idx_2]:
idx_1 += 1
else:
idx_2 -= 1
return ans
其他
原题leetcode链接：11.container-with-most-water - https://leetcode-cn.com/problems/container-with-most-water/description/ 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台 说明：leetcode 题解 | 每日一题🔥 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。
008. 字符串转换整数 (atoi) | Leetcode题解
004. 寻找两个正序数组的中位数 | Leetcode题解
如果觉得这篇文章还不错，来个【分享、点赞、在看】三连吧，让更多的人也看到~