LeetCode——Container With Most Water

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;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。

上一篇:UML:类图复习-鸡生蛋,蛋生鸡


下一篇:Javascript DOM编程艺术 语法部分