[Problem]
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.
[Analysis]
这题的主要思路是两边逼近。只需要抓住一个规律：固定较高一边时另一边不断逼近至比当前高度更高的位置，才有可能（不一定）形成更大的面积，即可在O(n)时间完成。
[Solution]
public class Solution { public int maxArea(int[] height) { int max = 0; int head = 0; int tail = height.length - 1; while (head < tail) { int currentArea = (tail - head) * (height[head] > height[tail] ? height[tail] : height[head]); max = currentArea > max? currentArea : max; /* * if height[head] > height[tail], tracking backwards from tail * if height[idx] <= height[tail], the max area between head and idx can‘t * exceed the max area between head and tail * Reason: in this case for any k < tail, * area(k, head) = (k - head) * min(height[k], height[head]) * area(tail, head) = (tail - head) * min(height[tail], height[head]) * area(k, head) < area(tail, head) * thus in this case move head until height[k] > height[head] to * get a possibly larger area */ if (height[head] > height[tail]) { int idx = tail; while (idx > head && height[idx] <= height[tail]) { idx--; } tail = idx; } else { int idx = head; while (idx < tail && height[idx] <= height[head]) { idx++; } head = idx; } } return max; } }
LeetCode #11 Container With Most Water (M)
原文：http://www.cnblogs.com/zhangqieyi/p/4865332.html