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