原题如下:
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 | # encoding:utf-8 |