LeetCode OJ Container With Most Water

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.

class Solution {
public:
	int maxArea(vector<int> &height) {
		int i = 0, j = height.size() - 1, ans = 0;
		while (i < j) {
			ans = max(ans, (j - i) * min(height[i], height[j]));
			if (height[i] < height[j]) i++;
			else j--;
		}
		return ans;
	}
};

如果j--，情况有如下两种：

1、新的height[j]比height[i]大，这是没有用的，装水面积取决于更短的height[i]，而且宽度（j-i）还减少了，这样新得到的面积必然变小；

2、新的height[j]比height[i]小，这就更没用了，容器的宽度（j-i）和高度都减少了，新得到面积必然减少；

所以，当height[i] < height[j]的时候，选择i++；

反之同理。

LeetCode OJ Container With Most Water

原文：http://blog.csdn.net/u012925008/article/details/44607243