第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0011. 盛最多水的容器
题目地址(11. 盛最多水的容器)
题目描述
1
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
2
3
说明：你不能倾斜容器，且 n 的值至少为 2。
4
5
6
7
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
8
9
10
11
示例：
12
`
13
输入：[1,8,6,2,5,4,8,3,7]
14
输出：49
Copied!
前置知识
- 双指针
公司
- 字节
- 腾讯
- 百度
- 阿里
思路
题目中说
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 ，因此符合直觉的解法就是固定两个端点，计算可以承载的水量， 然后不断更新最大值，最后返回最大值即可。这种算法，需要两层循环，时间复杂度是 $O(n^2)$。代码（JS）:
1
let max = 0;
2
for (let i = 0; i < height.length; i++) {
3
for (let j = i + 1; j < height.length; j++) {
4
const currentArea = Math.abs(i - j) * Math.min(height[i], height[j]);
5
if (currentArea > max) {
6
max = currentArea;
7
}
8
}
9
}
10
return max;
Copied!
虽然解法效率不高，但是可以通过（JS 可以通过，Python 不可以，其他语言没有尝试）。那么有没有更优的解法呢？
我们来换个角度来思考这个问题，上述的解法是通过两两组合，这无疑是完备的。我们换个角度思考，是否可以:
- 先计算长度为 n 的面积
- 然后计算长度为 n-1 的面积
- ...
- 计算长度为 1 的面积。
很显然这种解法也是完备的，但是似乎时间复杂度还是 $O(n ^ 2)$, 不要着急，我们继续优化。
考虑一下，如果我们计算 n-1 长度的面积的时候，是可以直接排除一半的结果的。
如图：
11.container-with-most-water
比如我们计算 n 面积的时候，假如左侧的线段高度比右侧的高度低，那么我们通过左移右指针来将长度缩短为 n - 1 的做法是没有意义的，因为
新形成的面积变成了(n-1) * heightOfLeft， 这个面积一定比刚才的长度为 n 的面积 （n * heightOfLeft） 小。也就是说最大面积一定是当前的面积或者通过移动短的端点得到。
关键点解析
- 双指针优化时间复杂度
代码
- 语言支持：JS，C++,Python
JavaScript Code:
1
/**
2
* @param {number[]} height
3
* @return {number}
4
*/
5
var maxArea = function (height) {
6
if (!height || height.length <= 1) return 0;
7
8
let leftPos = 0;
9
let rightPos = height.length - 1;
10
let max = 0;
11
while (leftPos < rightPos) {
12
const currentArea =
13
Math.abs(leftPos - rightPos) *
14
Math.min(height[leftPos], height[rightPos]);
15
if (currentArea > max) {
16
max = currentArea;
17
}
18
// 更新小的
19
if (height[leftPos] < height[rightPos]) {
20
leftPos++;
21
} else {
22
// 如果相等就随便了
23
rightPos--;
24
}
25
}
26
27
return max;
28
};
Copied!
C++ Code:
1
class Solution {
2
public:
3
int maxArea(vector<int>& height) {
4
auto ret = 0ul, leftPos = 0ul, rightPos = height.size() - 1;
5
while( leftPos < rightPos)
6
{
7
ret = std::max(ret, std::min(height[leftPos], height[rightPos]) * (rightPos - leftPos));
8
if (height[leftPos] < height[rightPos]) ++leftPos;
9
else --rightPos;
10
}
11
return ret;
12
}
13
};
Copied!
Python Code:
1
class Solution:
2
def maxArea(self, heights):
3
l, r = 0, len(heights) - 1
4
ans = 0
5
while l < r:
6
ans = max(ans, (r - l) * min(heights[l], heights[r]))
7
if heights[r] > heights[l]:
8
l += 1
9
else:
10
r -= 1
11
return ans
Copied!
复杂度分析
- 时间复杂度：由于左右指针移动的次数加起来正好是 n， 因此时间复杂度为 $O(N)$。
- 空间复杂度：$O(1)$。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago