你的位置:首页 > Java教程

[Java教程]No.011: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.

官方难度:

Medium

翻译:

给定n个非负整数a1,a2,...,an,每一个数值代表坐标轴上的坐标(i,ai)。

n条垂直于横坐标的竖线被画出,用于连接点(i,ai)和(i,0)。

找到两条线,与x轴一起形成一个容器,能够容纳最多的水。

注意:容器不能倾斜。

思路:

1.所谓容纳最多的水的容器,言下之意就是容积V=x轴间距*MIN(线1,线2)。

2.最简单的思想,用一个值记录最大容积,两次遍历,将算出的容积值依次与最大容积比较,大则覆盖,反之不动。

3.存在增加效率的方法。第一次正常遍历,第二次遍历可以取巧,使用反向遍历。因为反向遍历的情况下,x轴间距一定是越来越小的,使用一个变量记录达到最高容积时的长度,之后遍历到的长度只要低于记录值,就可以不必计算容积直接略过,进入下一次遍历。

解题中可能遇到的困难:

1.在使用优化的时候,注意将线2的最大长度的初始化工作放到内循环之外,因为每一次内循环结束后,长度需清0重新计算。

2.所谓的长度,是MIN(线1,线2)。

解题代码:

 1   private static int[] method(int[] array) { 2     int[] result = new int[2]; 3     int maxArea = 0; 4     for (int i = 0; i < array.length; i++) { 5       int maxHeight = 0; 6       // 第二次反向遍历 7       for (int j = array.length - 1; j > i; j--) { 8         int height = Math.min(array[i], array[j]); 9         // 因为底越来越小,所以只有高度大于最高高度,才有比较面积的意义10         if (height > maxHeight) {11           // 不考虑面积比较结果,高先赋值12           maxHeight = height;13           if (height * (j - i) > maxArea) {14             maxArea = height * (j - i);15             result[0] = i;16             result[1] = j;17           }18         }19       }20     }21     return result;22   }

View Code

测试代码地址:

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q011.java

LeetCode题目地址:

https://leetcode.com/problems/container-with-most-water/

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!