不知道这个应该起什么题目，目前还没想出有什么可以扩展的地方，暂且先把问题题目作为标题吧，日后若发现可扩展再进行补充。
题目描述：
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 and n is at least 2.
这道题若是以O（n2）的时间复杂度会超时，所以要想一个O（n）的方法。
算法描述：输入数组为int［］ height。初始化两个指针left和right，分别指向数组的首端和末端，比较height［left］和height［right］的值，若height［left］<height［left］则left右移，否则right左移，直到left＝＝right。整个过程中计算每一个得到的新容器的容积，留下最大的那个。
解释：
1.为什么要移动最小的指针呢？
举个例子，若此时left＝＝1，height［1］＝＝1，right＝9，height［9］＝＝9.此时容积等于Math.min（height［left］，height［right］）＊（right－left）＝8.
右指针right左移的话容积小于等于height［left］＊（right－1）＝7，必定比原容积小，因此右指针左移没有意义，是需要舍弃的。（此时放弃右指针左移而让左指针右移实际上是放弃了left>=1，同时right＝9的全部可能情况，因为这些情况的容积均比现在小）
左指针left右移的话容积不定，所以需要计算现在的容积，与之前的Max容积取最大值。（要想遍历所有可能取最大值的情况，此时也只能左指针右移了，因为右指针左移不可行，两个指针都不动没意义）
2.比如现在left＝＝2，right＝＝9，数组总长度13。可不可能最大值情况为left＝＝3，right＝＝11.但是right指针再也无法指向11了？因为现有的基础是right＝＝9而其又只能right－－。
不可能。因为每一步移动最大值均是不变或者增加，right曾经指向了11，那之后无论left等于多少，max取值只能大于等于righ＝＝11的时候。
PS：max=Math.max(max, Math.min(height[left], height[right])*(right-left))
附代码：
public class Solution {
public static int maxArea(int[] height) {
int left=0,right=height.length-1,max=0;
while(left<right)
{
max=Math.max(max, Math.min(height[left], height[right])*(right-left));
if(height[left]<height[right])
left++;
else
right--;
}
return max;
}
}
网友评论