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.
给定n个非负整数a1,a2,……,an,每一个代表坐标(i,ai)上的一个点,n条直线的两端各自是(i,ai) ,(i,0)。找出两条直线,使其与x轴形成一个容器,使容器包括最多的水。
注意:你不能够倾斜容器。
原题比較直白的解释大概如此:数组中的每一个元素代表一个水槽的边。找出两条边。使得水槽的体积最大。
这里不用考虑宽度,仅仅要 底 x 高 最大就可以。即两个水槽边的距离要越远。边的高度要越大,可是依据“木桶原理”。此处由高度较小的边决定。
就可以由两边向中间搜索,找到使得面积最大的两条边。
public int maxArea(int[] height) {
int area = 0;
int i = 0, j = height.length - 1;
while (i < j) {
area = Math.max(area, (j - i) * Math.min(height[i], height[j]));
if (height[i] > height[j])
j--;
else
i++;
}
return area;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。