题目要求
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.
题目翻译：给定n个非负整数，每一个代表一个坐标点如 ai 代表坐标点 （i, ai），对每一个点做垂直于x轴的线段，端点分别是（i, 0）和（i, ai）。现在，找出两条线段，它们和x轴组成的容器能盛下最多的水。
简而言之：根据木桶效应（容量取决于底面积乘以最短板的高度），两条线段较小的一条的高度，乘以它们之间在x轴方向上的距离，即是容量。找出最大容量。
题目分析
用两个for循环实现的O（n^2）算法超时。苦想不出优化解，参考LeetCode讨论区给出的O（n）算法，以下是该算法的证明和实现。
为了提高效率。我们需要在遍历的过程中剪去无用的情况同时100%保证最大的值能在我们余下的情况中获取到。
在这个问题中，我们初始化一左一右两个游标分别为数组的端点。每一次向数组的中间移动值较小的游标一步，直到两个游标相遇。这个过程中，最大容量100%会被扫描过并获取,以下是证明：
1、给定a1,a2,a3.....an作为输入，假设a10 和 a20是最大容量的情况。我们需要证明左游标会到达a10，并且在这期间，右游标可以到达a20，因此核心问题变成：当左游标在a10且右游标在a21时，下一步的移动是右游标指向a20。
2、因为我们总是移动带有较小值的游标，如果a10>a21，我们会移动把右游标从a21移动到a20。假设a21>a10，则height[a10] x (20-10) < height[a10] x (21-10)，与1中假设a10和a20是最大容量不符，因此一定有a10>a21。
3、综上所述：左游标会到达a10，并且在这期间，右游标可以到达a20，由此证明，该算法100%能获取到最大值。
代码实现
package com.linsiyue;
public class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
maxArea = Math.max(maxArea,
Math.min(height[left], height[right]) * (right - left));
if (height[left] < height[right])
left++;
else
right--;
}
return maxArea;
}
}
心得总结
对于最优解搜索问题，直接的思路是分析如何求得最优解，但是有时候思路没那么好找；我们可以试着通过假设去固定最优解（如本题中假设a10 和 a20是最大区域），通过分析最优解具备的性质（a10>a21），找到并实现这些性质就找到了最优解，这是反向求解法。
