- 指针初始化：left指向数组开头，right指向数组末尾，此时宽度最大。
- 贪心移动（利用单调性）：每次计算当前容器的盛水量（较短边高度 × 两指针距离），并更新最大值。然后移动较短边对应的指针 ——因为移动较长边只会让宽度减小而高度不可能增加，容量必然变小；移动较短边才有机会遇到更高的边来弥补宽度损失。
代码
public class MaxContainer {
public int maxArea(int[] height) {
int left=0,right=height.length-1;
int max=0;
for (int i = 0; i < height.length; i++) {
int len=right-left;
if(height[left]<height[right]){
int ret=0;
ret=len*height[left];
if(ret>max){
max=ret;
}
left++;
}else {
int ret=0;
ret=len*height[right];
if(ret>max){
max=ret;
}
right--;
}
}
return max;
}
public static void main(String[] args) {
int[] height={1,8,6,2,5,4,8,3,7};
MaxContainer maxContainer=new MaxContainer();
System.out.println(maxContainer.maxArea(height));
}
}
2 个帖子 - 2 位参与者
来源: linux.do查看原文