题干:

难度:Medium

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

解析:

这一题首先可以想到暴力解法,而一般公认推荐的解法是双指针法,实现起来非常简单,我在这里想简单证一下双指针法的正确性:
双指针法中移动的始终是数值较小的那个指针,那么如果说双指针法会出现错误,那一定是出现了对较大值的遗漏,比如,我们从下标i,m(i<m)开始向内进行双指针法,其中List[i]<List[m],我们从i开始向右移动指针,当找到List[j]>List[m]时,m对应的指针向左移动,那么这个过程中,什么样的值可能会被遗漏呢?我们只可能担心m之后有比Lit[m]更大的值List[n]出现,那么我们先移动了i,这样就可能有较大的面积值被遗漏。但是,实际上容器面积是取决于较小的那个值的(短板原理?),较大的那一端无论多大,两个值对应的容器的容积都只与较小的那一端有关,即,List[m]小于List[n],[i,j)之间对应n的容积对于m只可能会变得更小,所以不会有遗漏的更大容积值,所以双指针法的正确性是可以保证的.

Python解法

class Solution:
    def maxArea(self, height: List[int]) -> int:
        bef=0;beh=len(height)-1
        max=0
        while bef<beh:
            if(beh-bef)*min(height[bef],height[beh])>max:
                max=(beh-bef)*min(height[bef],height[beh])
            if height[bef]>height[beh]:
                beh=beh-1
            else:
                bef=bef+1
        return max
最后修改:2020 年 02 月 08 日 10 : 33 AM