Repository navigation
11.盛水最多的容器 #2
Description
虽然是中等难度，但这道题解起来还是比较简单的，老规矩，我们看下符合第一直觉的暴力法：
暴力法
幼儿园数学题：矩形面积 = 长 * 宽
放到我们这道题中，矩形的长和宽就分别对应：
- 长：两条垂直线的距离
- 宽：两条垂直线中较短的一条的长度
双重 for 循环遍历所有可能，记录最大值。
const maxArea = function(height) {
let max = 0 // 最大容纳水量
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
// 当前容纳水量
let cur = (j - i) * Math.min(height[i], height[j])
if (cur > max) {
max = cur
}
}
}
return max
}- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
暴力法时间复杂度 O(n^2) 太高了，我们还是要想办法进行优化。
双指针
我们可以借用双指针来减少搜索空间，转换为双指针的视角后，回顾矩形的面积对应关系如下：
(矩形面积)容纳的水量 = (两条垂直线的距离)指针之间的距离 * (两个指针指向的数字中的较小值)两条垂直线中较短的一条的长度
设置两个指针，分别指向头和尾(i指向头，j指向尾)，不断向中间逼近，在逼近的过程中为了找到更长的垂直线：
- 如果左边低，将i右移
- 如果右边低，将j左移
有点贪心思想那味儿了，因为更长的垂直线能组成更大的面积，所以我们放弃了较短的那一条的可能性。
但是这么做，我们有没有更能漏掉一个更大的面积的可能性呢？
先告诉你答案是不会漏掉。
关于该算法的正确性证明已经有很多同学们给出了答案，感兴趣的请戳下面链接。
const maxArea = function(height) {
let max = 0 // 最大容纳水量
let left = 0 // 左指针
let right = height.length - 1 // 右指针
while (left < right) {
// 当前容纳水量
let cur = (right - left) * Math.min(height[left], height[right]);
max = Math.max(cur, max)
height[left] < height[right] ? left ++ : right --
}
return max
};- 时间复杂度：O(n)
- 空间复杂度：O(1)
Activity