Leetcode 11 Container With Most Water

发表于 |

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

说明：你不能倾斜容器，且 n 的值至少为 2。

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

题意分析：
选择两条线段，使其与x轴构成的容器的容量最大

思路分析：
我们知道容器的容量取决于底部长度和两边中较短的那一边的长度。
想让容量变大有两种方式，一种是增加底部长度，另一种是增加较短的边的长度。

我们首先先将底部长度最大化，即长度为n，n为数组长度。
在这个基础上，我们想将容量继续扩大，就只能是增加较短边的长度了。
当然，由于想增加较短边的长度就必须缩短底部长度，所以并不能保证何时能取得最大容量，我们需要每次都记录一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 60ms, beats 18.72%
class Solution(object):
    def maxArea(self, nums):
        res = 0
        n = len(nums)
        # 初始化底部长度，使其最大
        i,j = 0,n-1
        while i < j:
            h = min(nums[i], nums[j])
            res = max(res, (j-i)*h)
            # 判断哪一条边是较短边，然后使其增大
            if h == nums[i]:
                while i < j and nums[i] <= h: i += 1
            elif h == nums[j]:
                while i < j and nums[j] <= h: j -= 1
        return res