LeetCode解题报告(11)--双指针找最大储水容器

发表于 标签 ，

原题如下： >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.

这道题的不难理解，但是对时间复杂度有要求。简单地通过两个for循环寻找最大的蓄水量的时间复杂度为O(n^2),提交时提示超时。

蓄水量由container 的底（也就是两个下标之差）乘上其两端的边的最小值。假如left 为第一条竖直边的下标，right 为最后一条竖直边的下标，i,j为其中的两条边（设i < j），那么：

要使任何S(i>=left, j<=right) >= S(left,right)，由于j-i <= right-left，必然要有min(ai,aj)>=min(a(left),a(right))才行

因此可以从两边同时开始往中间逼近，每次只移动一步（左边的边或右边的边），而且两条边中最短的边进行移动。时间复杂度为O(n)，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# encoding:utf-8

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = 0
        right = len(height) - 1
        max = 0
        while left < right:
            current = (right - left)* min(height[left],height[right])
            if current >max:
                max = current
            if height[left] > height[right]:
                right-=1
            else:
                left+=1
        return max