011. Container With Most Water

leetcode 11.盛最多水的容器

给定n个非负整数a1,a2,...,an，其中每个代表一个点坐标（i,ai）。

n个垂直线段例如线段的两个端点在（i,ai）和（i,0）。

找到两个线段，与x轴形成一个容器，使其包含最多的水。

备注：你不必倾倒容器。

暴力

$O(n^2)$的复杂度。

class Solution {
public:
	int maxArea(vector<int>& height) {		//暴力写一个先
		int maxWater = 0,dataSize = height.size();
		for (int i = 0; i < dataSize; i++) {
			for (int j = i + 1; j < dataSize; j++) {
				maxWater = max(maxWater, min(height[i], height[j])*abs(i-j));
			}
		}
		return maxWater;
	}
};

肯定时间会超限

双指针法

O(n)的复杂度。

保持两个指针i,j,分别指向长度数组的首尾。

• 如果height[i] 小于height[j]，则移动i向后（i++）。
• 反之，移动j向前（j—）。
• 如果当前的maxWater 大于了所记录的maxWater ，替换之。

这个想法的基础是，如果i的长度小于j，无论如何移动j，短板在i，不可能找到比当前记录的area更大的值了，只能通过移动i来找到新的可能的更大面积。

class Solution { //传说中的左右指针，
public:
	int maxArea(vector<int>& height) {
		if (height.size() < 2)return 0;
		int i = 0, j = height.size() - 1;
		int maxWater = 0;
		while (i < j) {
			maxWater = max(maxWater, min(height[i], height[j])*abs(i - j));
			if (height[i] < height[j]) i++;
			else j--;
		}
		return maxWater;
	}
};