LeetCode 11. 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.

Seen this question in a real interview before?

Yes

很有意思的一道题目求下图vector中的元素表示线段长度，向量元素下标表示线段的位置，我们需要找到到两条线段，使得较短线段与线段距离乘积最大，这也就是文中说的“容器中水的容量”

这道题最直接的思路就是暴力搜索，枚举所有可能的情况，很直接的思路，但是会超时，代码如下：

 1 class Solution {
 2 public:
 3     int maxArea(vector<int>& height) {
 4         int res = 0;
 5         for (int i = 0; i < height.size(); i++)
 6         {
 7             for (int j = i+1; j < height.size(); j++)
 8             {
 9                 res = max(res, min(height[i], height[j]) * (j - i));
10             }
11         }
12         return res;
13     }
14 };

时间复杂度:O(n^2)

空间复杂度：O(1)

我们换一种思路，两个指针一头一尾，每次向内移动较短的那个线段，同时记录下来每次的面积，官方的解释是这么做有可能找到新的比最短线段更长的线段弥补水平距离（矩形的宽）的减少，但是我个人认为这么做还是缺乏严格的数学证明，可以AC代码如下：

 1 class Solution {
 2 public:
 3     int maxArea(vector<int>& height) {
 4         int lo = 0, hi = height.size() - 1;
 5         int res = 0;
 6         while (lo < hi)
 7         {
 8             res = max(res, min(height[lo], height[hi])* (hi - lo));
 9             if (height[lo] < height[hi])
10                 lo++;
11             else
12                 hi--;
13         }
14         return res;
15     }
16 };

或者少调用几次max min函数，加快一点速度

 1 class Solution {
 2 public:
 3     int maxArea(vector<int>& height) {
 4         int i = 0;
 5         int j = height.size() - 1;
 6         int max_a = 0;
 7         while (i<j)
 8         {
 9             if(height[i] < height[j])
10             {
11                 if(max_a < (j - i)*height[i]) max_a = (j - i)*height[i];
12                 i++;
13             }
14             else
15             {
16                 if(max_a < (j - i)*height[j]) max_a = (j - i)*height[j];
17                 j--;
18             }
19         }
20         return max_a;
21     }
22 };

时间复杂度: O(n)

空间复杂度：O(1)