打卡，第四天

今天的题目是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
int maxArea(vector<int> &height) {
2
  int water = 0;
3
  for(int i = 0;i < height.size(); ++i)
4
    for (int j = 0;j < height.size(); ++j) {
5
      int h = min(height[i],height[j]);
6
      water = max(water,h*(j - i));
7
    }
8
  return water;
9
}

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

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

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

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

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