盛水最多的容器
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
永远去移动两根柱子中较高的那个的指针。
这里我们先去看假设不去移动矮柱子反而去移动高柱子会发生什么。最开始两个指针指向头和尾两个柱子,假设移动高柱子的指针,则两个柱子之间的距离会变短。
- 下一个柱子的高度比之前的高度矮。则面积一定会变小。因为两根柱子之间的距离变短了,能够装水的高度还变矮了,所以能装的水一定会变少。这点比较好理解。
- 下一个柱子的高度比之前高。两根柱子之间的距离还是会缩短,这点没有疑问。但是能装多高的水是矮柱子决定的,尽管新柱子的高度更高,但是能装水的高度还是和原来一样,因为我们移动了高柱子的指针。距离变短,高度不变,能装的水还是会变少。
按照这个思路分析移动矮柱子就会发现。如果碰到更矮的柱子肯定能装的水更少;但是如果有更高的柱子,就变成了柱子距离变短,但是能装水的高度增加了。这种情况是可能出现能装更多的水的,这也是为什么要移动矮柱子。
var maxArea = function(height) {
let max = 0, left = 0, right = height.length - 1
while (left < right) {
const area = (right - left) * Math.min(height[left], height[right])
max = Math.max(area, max)
if (height[left] < height[right]) {
left++
} else {
right--
}
}
return max
};