1.题目描述
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器。
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
2.问题分析
该问题想得到，一个最大值：即数组中两个元素中较小的值和其下标之差的值的最大值。
（1）暴力法
最简单的解法，即是遍历问题的全部解，找出最大值。即两层循环，计算各个元素的较小值和其下标之差的结果，取得最大值。但问题中有大规模输入，对问题的时间复杂度有要求。
该方法下的时间复杂度为O（n^2）
（2）高低排序法
暴力法会造成超时，现思考一优化的方法。先将整个数组用快速排序排序，并记录排序后的数组中每个元素之前的位置（排序后会打乱顺序）。然后从第一个最小的元素开始，它将不再需要和元素比较大小。
用它自身的值，依次和后面的元素与它的下标之差相乘，得到它这一层的最大值。最终得到最值。
该算法的时间复杂度为O（n*logn）+O(n*(n-1)/2) ≈ O(n^2)，虽然具体实例的时间快于O（n^2）。但没有实质性的提高，该方法也会造成超时。
（3）首尾指针法
在算法二中已经思考到了，控制一个变量的顺序，比较另一个变量。但忽略了题中每个元素的下标长度已经排序好了，而且数组元素数值的大小仅需比较即可。那么设置首尾指针，比较得值，将较小元素
的指针向前或向后移，直到首尾指针相遇。
3.代码
由于1.3代码实现简单，不再记录，而问题二虽然没有达到响应的效果，但做了排序顺序记录，仅记录2代码
import java.util.ArrayList; /** * @author 帆哥续写辉煌 */ public class Solution { public int maxArea(int[] height) { int maxsize = 0; int [] pos = new int[height.length]; for(int i=0;i<pos.length;i++){pos[i]=i;} quickSort(height,0,height.length-1,pos); for(int i=0;i<height.length;i++){ int maxDistance = 0; for(int j=i+1;j<height.length;j++){ maxDistance = Math.max(Math.abs(pos[j]-pos[i]),maxDistance); } maxsize = Math.max(height[i]*maxDistance,maxsize); } return maxsize; } private void quickSort(int[] height,int start,int end,int[]pos){ int i=start; int j=end; while (i<j){ while (height[j]>=height[i]&&i<j){ j--; } int temp = height[i]; int tempPos = pos[i]; height[i] = height[j]; height[j] = temp; pos[i] =pos[j]; pos[j]= tempPos; while (height[i]<=height[j]&&i<j){ i++; } temp = height[i]; tempPos = pos[i]; height[i] = height[j]; height[j] = temp; pos[i] =pos[j]; pos[j]= tempPos; } if(start<i){ quickSort(height,start,i-1,pos); } if(end>i){ quickSort(height,i+1,end,pos); } } }