跳到主要内容

11. 盛最多水的容器

题目描述​

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

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

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

说明：你不能倾斜容器。

示例 1:

示例 1

输入: [1,8,6,2,5,4,8,3,7]

输出: 49

**解释 **: 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2:

输入: height = [1,1]

输出: 1

提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

出处：LeetCode

解法一：暴力法​

思路​

我们可以使用两层循环枚举所有的容器，计算每个容器的容量，然后取最大值。

代码​

function maxArea(height: number[]): number {
  let max = 0;
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      const area = Math.min(height[i], height[j]) * (j - i);
      max = Math.max(max, area);
    }
  }
  return max;
}

复杂度分析​

  • 时间复杂度：O(n2)O(n^2)，其中 nn 是数组的长度。
  • 空间复杂度：O(1)O(1)。

解法二：双指针​

思路​

我们使用两个指针 left 和 right 分别指向数组的左右两端。假设 left 指向的元素小于 right 指向的元素，那么此时容器的容量为 height[left] * (right - left)。为了使容器的容量最大，我们需要尽量增大容器的宽度，因此我们移动 left 指针。如果 left 指向的元素大于 right 指向的元素，那么我们移动 right 指针。直到 left 和 right 指针相遇。

代码​

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let max = 0;
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    max = Math.max(max, area);
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return max;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是数组的长度。
  • 空间复杂度：O(1)O(1)。