盛最多水的容器

1、题目描述

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

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

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

说明:你不能倾斜容器。

示例 1:

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

示例 2:

1
2
输入:height = [1,1]
输出:1

提示:

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

2、题解

2.1 双指针

  • 题目中的示例为:

    1
    2
    [1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^ ^
  • 在初始时,左右指针分别指向数组的左右两端,它们可以容纳的水量为 min(1,7)∗8=8。

  • 此时我们需要移动一个指针。移动哪一个呢?直觉告诉我们,应该移动对应数字较小的那个指针(即此时的左指针)。这是因为,由于容纳的水量是由:两个指针指向的数字中较小值∗指针之间的距离决定的。如果我们移动数字较大的那个指针,那么前者「两个指针指向的数字中较小值」不会增加,后者「指针之间的距离」会减小,那么这个乘积会减小。因此,我们移动数字较大的那个指针是不合理的。因此,我们移动 数字较小的那个指针

  • 所以,我们将左指针向右移动:

    1
    2
    [1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^ ^
  • 此时可以容纳的水量为 min(8,7)∗7=49。由于右指针对应的数字较小,我们移动右指针:

    1
    2
    [1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^ ^
  • 此时可以容纳的水量为 min(8,3)∗6=18。由于右指针对应的数字较小,我们移动右指针:

    1
    2
    [1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^ ^
  • 此时可以容纳的水量为 min(8,8)∗5=40。两指针对应的数字相同,我们可以任意移动一个,例如左指针:

    1
    2
    [1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^ ^
  • 此时可以容纳的水量为 min(6,8)∗4=24。由于左指针对应的数字较小,我们移动左指针,并且可以发现,在这之后左指针对应的数字总是较小,因此我们会一直移动左指针,直到两个指针重合。在这期间,对应的可以容纳的水量为:min(2,8)∗3=6,min(5,8)∗2=10,min(4,8)∗1=4。

  • 在我们移动指针的过程中,计算到的最多可以容纳的数量为 49,即为最终的答案。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    from typing import List


    class Solution(object):
    def maxArea(self, height: List[int]) -> int:
    l, r = 0, len(height) - 1
    ans = 0
    while l < r:
    area = min(height[l], height[r]) * (r - l)
    ans = max(ans, area)
    if height[l] <= height[r]:
    l += 1
    else:
    r -= 1
    return ans


    solution = Solution()
    print(solution.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public class Solution {
    public int maxArea(int[] height) {
    int l = 0, r = height.length - 1;
    int ans = 0;
    while (l < r) {
    int area = Math.min(height[l], height[r]) * (r - l);
    ans = Math.max(ans, area);
    if (height[l] <= height[r]) {
    ++l;
    } else {
    --r;
    }
    }
    return ans;
    }
    }
  • 复杂度分析

    • 时间复杂度:O(N),双指针总计最多遍历整个数组一次。
    • 空间复杂度:O(1),只需要额外的常数级别的空间。