LeetCode 11. Container With Most Water

Description:

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.

分析：

题目大意：给出一组非负数，作为一个数组height，height[i] = h表示横坐标为i的高位h，以（i，h）与x轴作垂线段，计算两条垂线段和x轴组成的容器最大的容积。
首先尝试暴力破解法：两层循环，比较数组值的大小，选择小的数值作为高，内层循环下标j减去外层循环i作为宽，不断更新res结果，具体代码见下面，但该方法耗时大，时间复杂度为$O(n^2)$，提交后超时了。
所以，我们有了更好的一个方法，从数组两边开始，每次取最短的边（也就是值较小）作为高，假设有left和right两个变量，left从数组左边开始（也就是0），right从右边开始（也就是height.size()-1），先求得当前容器容积的最大值，然后比较左边和右边的高，如果左边小则left++，如果右边小则right--，直到left==right退出循环，得到最大容积结果res。

代码如下：

Time Limited版本：

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

Accept版本：

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