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 and n is at least 2.

相当于要找数组中的某两个数，使得这两个数的间距与两数中的较小数的乘积取最大值。比较直接的方法是遍历，时间复杂度为O(n^2)。若要智取，可以考虑不断缩减两个数的间距，通过减小长度，增加高度的方法增大面积。两个数中，哪个数更大，就向那一边移动。

两个数相等怎么办呢？两边方向都可以。因为最终高度取决于较小的数，而两个等高的柱子之间，要么比他们更高，但距离更小；要么高度和距离都更小。唯一可能增大面积的情况是等高柱子中间的两个最大的数组合，但无论从哪一边移动，都会遇到这个情况，不会被遗漏。这样的方法每个数只遍历一遍，时间复杂度为O(n)。

解决方案

int maxArea(vector<int>& height) {
	int len = height.size()-1;
	int left = 0;
	int right = len;
	int max = 0;
	int low = height[0];
	while (len > 0)
	{
		if (height[left] < height[right])
		{
			low = height[left];
			max = max > low*len ? max : low * len;
			++left;
		}
		else
		{
			low = height[right];
			max = max > low*len ? max : low * len;
			--right;
		}
		--len;
	}
	return max;
}