# 0011. 盛最多水的容器
### 题目地址(11. 盛最多水的容器)
### 题目描述
```
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：
`
输入：[1,8,6,2,5,4,8,3,7]
输出：49
```
### 前置知识
* 双指针
### 公司
* 字节
* 腾讯
* 百度
* 阿里
### 思路
题目中说`找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。` ，因此符合直觉的解法就是固定两个端点，计算可以承载的水量， 然后不断更新最大值，最后返回最大值即可。这种算法，需要两层循环，时间复杂度是 $O(n^2)$。
代码（JS）:
```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 的面积。
很显然这种解法也是完备的，但是似乎时间复杂度还是 $O(n ^ 2)$, 不要着急，我们继续优化。
考虑一下，如果我们计算 n-1 长度的面积的时候，是可以直接排除一半的结果的。
如图：
比如我们计算 n 面积的时候，假如左侧的线段高度比右侧的高度低，那么我们通过左移**右指针**来将长度缩短为 n - 1 的做法是没有意义的，因为`新形成的面积变成了(n-1) * heightOfLeft， 这个面积一定比刚才的长度为 n 的面积 （n * heightOfLeft） 小`。
也就是说**最大面积一定是当前的面积或者通过移动短的端点得到。**
### 关键点解析
* 双指针优化时间复杂度
### 代码
* 语言支持：JS，C++,Python
JavaScript Code:
```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;
};
```
C++ Code:
```
class Solution {
public:
int maxArea(vector& 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;
}
};
```
Python Code:
```py
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
```
**复杂度分析**
* 时间复杂度：由于左右指针移动的次数加起来正好是 n， 因此时间复杂度为 $O(N)$。
* 空间复杂度：$O(1)$。
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/11.container-with-most-water.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.