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.
Solution
(Container-with-Most-Water.java) download 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int maxArea ( int [] height ) {
int water = 0 ;
int left = 0 ;
int right = height . length - 1 ;
while ( left < right ){
int h = Math . min ( height [ left ], height [ right ]);
water = Math . max ( water , h *( right - left ));
while ( height [ left ] <= h && left < right ) left ++;
while ( height [ right ] <= h && left < right ) right --;
}
return water ;
}
}
时间复杂度O（n），两个指针i, j分别从前后向中间移动，两个指针分别表示容器的左右边界。每次迭代用当前的容量更新最大容量，然后把高度小的边界对应的指针往中间移动一位。 本文地址
正确性证明：由于水的容量是有较小的那个边界决定的，因此某次迭代中，假设height[i] < height[j]，那么j 减小肯定不会使水的容量增大，只有i 增加才有可能使水的容量增大。但是会不会有这种可能：当前的i 和 某个k (k > j)是最大容量, 这也是不可能的，因为按照我们的移动规则，既然右指针从k 移动到了j，说明i 的左边一定存在一个边界 m，使m > k，那么[m, k]的容量肯定大于[i, k]，所以[i,k]不可能是最大容量。
(Container-with-Most-Water.py) download 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution ( object ):
'''
题意:任取两个a[i]、a[j] 使得min(a[i], a[j]) * abs(i - j)最大化
用两个指针从两侧向中间扫描，每次移动数值较小的指针，用反证法可以证明
总是可以得到最优答案
'''
def maxArea ( self , height ):
left , right = 0 , len ( height ) - 1
ans = 0
while left != right :
if height [ left ] < height [ right ]:
area = height [ left ] * ( right - left )
left += 1
else :
area = height [ right ] * ( right - left )
right -= 1
ans = max ( ans , area )
return ans