认识达内从这里开始

昆明Java培训班的老师今天给大家讲怎么做水的容器。

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

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

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

注意：容器不能倾斜。

昆明Java培训班的老师的思路：

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    }

测试代码地址：

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

LeetCode题目地址：

#/problems/container-with-most-water/

了解详情请登陆昆明达内Java培训官网（km.Java.tedu.cn）！