[LeetCode]Container with Most Water

又是双指针的问题，我们以下图为例子进行说明：

首先我们开始的两个指针i，j分别指向1和9，当我们计算过1和9所围成的面积之后，1和剩余所有墙壁所围成的面积都不可能大过和9围成的面积，我们左移1到2，2的高度大于1所以2和9围成的面积有可能大于之前所计算的值。2的高度仍然小于9，根据之前的解释，我们移动2，但是我们没有必要去check 3和4因为3和4的高度比2还要小，面积更小，然后我们移到5，5的高度大于2的高度，有可能面积更大，我们一直这么做直到i >= j。

所以我们的策略是，哪边高度更小，我们移动哪边的指针直到找到一个比当前高度更高的值，然后重复之前的步骤。时间复杂度是O(n)，空间复杂度是O(n)，代码如下：

	public class Solution {
	public int maxArea(int[] height) {
	if (height == null)
	return 0;
	int len = height.length, i = 0, j = len - 1;
	int max = 0;
	while (i < j) {
	int left = height[i], right = height[j], hei = left <= right? left: right;
	int area = hei * (j - i);
	max = area > max? area: max;
	if (left <= right) {
	while (i < j && height[i] <= left)
	i++;
	} else {
	while (i < j && height[j] <= right)
	j--;
	}
	}
	return max;
	}
	}

view raw container with most water.java hosted with ❤ by GitHub