Container With Most Water

LeetCode

打卡，第四天

今天的题目是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.

很烦，今天老是时间超限，就是不能想出一个时间复杂度小的算法来。

先理解一下题目先，大概就是给你一个数组height，你要找出两个i，j使得min(height[i],height[j])*(j - i)最大。

很容易写出一个$ O(n^{2}) $ 的算法出来：

1
2
3
4
5
6
7
8
9
int maxArea(vector<int> &height) {
	int water = 0;
	for(int i = 0;i < height.size(); ++i)
		for (int j = 0;j < height.size(); ++j) {
			int h = min(height[i],height[j]);
			water = max(water,h*(j - i));
		}
	return water;
}

但是这个算法是不能过最后一个测例的。

想了一个小时都没想出一个好方法来减少他的复杂度,后来就去翻dicuss，看到这样一个算法：

1
2
3
4
5
6
7
8
9
10
int maxArea(vector<int> &height) {
	int water = 0;
	int i = 0,j = height.size() - 1;
	while(i < j) {
		int h = min(height[i],height[j]);
		water = max(water,h*(j - i));
		while(height[i] <= h && i < j) i++;
		while(height[j] <= h && i < j) j++;
	}
}

这里是先取最宽的容器，假设他就是我们要的结果。
因为i不断变大,j不断变小，这样wide就不断变小，因为wide在变小，要比当前最大的容器还大的话就只能比当前高度高，这就是那两个while的作用，去除掉一个不可能的情况。

啊，我真菜，为什么老是想不出来呢！