盛最多水的容器

Leetcode算法题 11 Posted by Haoran Bai on April 17, 2020 · 1 min read

盛最多水的容器 [Link]

Leetcode 4月每日一题合集

1. 题目描述

给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai)(i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2

盛最多水的容器

示例 1:

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

2. 题解与思路

采用 双指针 的思路,维护两个指针 lr,表示盛水容器的左壁和右壁,初始时,两个指针分别在最左侧和最右侧,我们要做的就是缩小这个容器,然后挑出容量最大的容器。

所以算法的思路就是:

  • l<r 时,就计算当前容器的容量,计算方式为 min(height[l], height[r]) * (r-l),然后记录当前容量最大值。
  • 然后缩小容器,到底该移动哪个指针呢?结论是:应该移动 height 小的指针。

移动 height 小的指针的原因:假设 height[l]<height[r],由于接下来遍历的容器的长度 r-l 是在减小的,如果保持 l 作为容器的左壁,那么接下来的容器的容量都不会超过当前容器的容量,所以没有必要保持 l 作为容器的左壁,所以应该移动 l

3. 代码

本解法 Python 代码如下

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l, r = 0, len(height)-1  # 左右两个指针
        max_water = 0
        while l<r:
            this_water = min(height[l], height[r]) * (r - l)  # 当前容器容量
            max_water = max(max_water, this_water)  # 记录当前容量最大值
            if height[l] <= height[r]:  # 移动 `height` 小的指针
                l += 1
            else:
                r -= 1
        return max_water