吴良超的学习笔记

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