[LeetCode] 11. Container With Most Water 题解

问题描述

输入 n 个非负整数 a1, a2, …, an,每个整数代表一个坐标点 (i,ai)(i, a_i),以每个点垂直于 x 轴作垂线,在其中找出 2 条垂线,再加上 x 轴,使这 3 条线围成的容器能容纳最多的水。

**注意:**容器不可以倾斜,且 n 不少于 2。

例子:

question_11

上图的垂线和数组 [1,8,6,2,5,4,8,3,7] 对应,如图可知,容器最大可容纳水位为 49

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

问题难度

Medium

解题思路

方法1:暴力法 (Brute Force)

这种方法很容易想到,即所有垂线的两两组合,计算它们可容纳的水位,经过比较,可得到最大值;该方法的时间复杂度为 O(n2)O(n^2),代码如下,注意,这段代码放到 LeetCode 上跑会超时的。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        m = 0
        for i in range(0, len(height)-1):
            for j in range(i+1, len(height)):
                m = max(m, (j-i)*min(height[i], height[j])) 
        return m

方法2:两端逼近法

从上图可以看出,水位的大小由短的那根垂线决定,这根短的线段变长,水位就会变大;沿这个思路,我们使用两个游标,第一个游标指向最左端的垂线,第二个指向最右端的垂线,在计算完水位后,比较这两根垂线的长度,然后移动指向较短垂线的游标,将其向中间移动。按照这种方法,不断逼近两个游标,最终在 O(n) 的时间复杂度便可以找到最大水位。

移动指向较短垂线的游标,更有可能使水位变大,因为游标下一次可能会指向一个更长的垂线。

代码如下:

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_area = 0
        left = 0
        right = len(height) - 1
        while left < right:
            h = min(height[left],height[right])
            max_area = max(max_area, (right - left)*h)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

原题链接