盛水最多的容器

盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i])

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

永远去移动两根柱子中较高的那个的指针。

这里我们先去看假设不去移动矮柱子反而去移动高柱子会发生什么。最开始两个指针指向头和尾两个柱子,假设移动高柱子的指针,则两个柱子之间的距离会变短。

  1. 下一个柱子的高度比之前的高度矮。则面积一定会变小。因为两根柱子之间的距离变短了,能够装水的高度还变矮了,所以能装的水一定会变少。这点比较好理解。
  2. 下一个柱子的高度比之前高。两根柱子之间的距离还是会缩短,这点没有疑问。但是能装多高的水是矮柱子决定的,尽管新柱子的高度更高,但是能装水的高度还是和原来一样,因为我们移动了高柱子的指针。距离变短,高度不变,能装的水还是会变少。

按照这个思路分析移动矮柱子就会发现。如果碰到更矮的柱子肯定能装的水更少;但是如果有更高的柱子,就变成了柱子距离变短,但是能装水的高度增加了。这种情况是可能出现能装更多的水的,这也是为什么要移动矮柱子。

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
};
上次更新:: 2024/1/16 11:26:08