LeetCode 「中等」11.盛最多水的容器

盛最多水的容器open in new window

题目描述

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

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

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

说明：你不能倾斜容器。

示例

输入：[1,8,6,2,5,4,8,3,7]
输出：49

输入：height = [1,1]
输出：1

解答

双指针

思路

1. 使用两个指针，一个指向数组的起始位置 left，另一个指向数组的末尾位置 right
2. 计算当前两个指针之间的水量，公式为：min(height[left], height[right]) * (right - left)
3. 每次移动较短的那根指针，因为移动较短的指针有可能找到更高的柱子，从而增加水量
4. 重复上述步骤，直到两个指针相遇

为什么移动较短的指针

• 移动较高的指针，宽度会变小，而高度不会增加，因此水量只会减少或不变
• 如果移动较短的指针，虽然宽度会变小，但有可能找到更高的柱子，从而增加水量

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
  let lk = 0, rk = height.length - 1;
  let maxvol = 0;

  while (lk < rk) {
    maxvol = Math.max(
      maxvol,
      Math.min(height[lk], height[rk]) * (rk - lk)
    );
    if (height[lk] > height[rk]) --rk;
    else ++lk;
  }

  return maxvol;
};