分类: Java
2015-03-22 14:36:00
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.
思路:两边设一个指针,然后计算area,如果height[i] <= height[j],那么i++,因为在这里height[i]是瓶颈,j往里移只会减少面积,不会再增加area。
这是一个贪心的策略,每次取两边围栏最矮的一个推进,希望获取更多的水。
(2个)针对当height[i] <= height[j]时,为什么是i++,而不是j++来获取可能更多的水?(i--同理)
假设j' > j,之所以j'往左移,是因为存在height[i'] > height[j'] (i’ <= i), 而那时area' = (j' - i') * min(height[i'], height[j']),
因为height[j'] == min(height[i'], height[j']),所以area' = (j' - i') * height[j']。
而i 和 j'构成的面积area = (j' - i) * min(height[i], height[j'])。
public int maxArea(int[] height) {
int i=0;
int j=height.length-1;
int result=0;
while(i
result=(result>=area)?result:area;
if(height[i]>height[j])
j--;
else {
i++;
}
}
return result;