问题描述

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.

实现

本来是想到的最简单直接的方法，两重循环，第一重循环是用来确定容器的左边边界，第二重循环是确定容器的右边边界。这样会超时，所以必须想一种时间复杂度要好于O(n^2)的方法解决这个问题。

参照前面的2-sum问题，可以想到，维护两个指针，指向开头和结尾，因为容器的容量是受到低的一边的边界的限制。那扩大一个容器的容量的方法，就是加大容器低的一端的高度。这样就算容器的宽度降低，但是也有可能本身的容量是增加的，根据这样的方法可以实现出一个线性时间复杂度的算法。就是不停缩小低的那一边，直到左右边界重合。

int maxArea(vector<int> &height) 
{
	int start = 0;
	int end = height.size() - 1;
	int maxArea = (end - start) * (min(height[start], height[end]));
	while (start + 1 < end)
	{
		if (height[start] > height[end])
		{
			end--;
			if (height[end] > height[end + 1])
				maxArea = max(maxArea, (end - start) * min(height[start], height[end]));
		}
		else
		{
			start++;
			if (height[start] > height[start - 1])
				maxArea = max(maxArea, (end - start) * min(height[start], height[end]));
		}
	}
	return maxArea;
}

倾斜容器

对于容器可以倾斜的情况，似乎并没有很好的方法可以解决。因为这个情况下没有什么可以用来简化问题的观察可得到的现象。起码我还是不知道如何简化问题，可能是物理不够好吧= =