题目链接：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.

这道题的要求是给定整形数组a，(i, ai)表示坐标点，这些坐标点向x轴作垂直的线。找到两条线，使其和x轴共同构成的容器，可以装下最多的水。（注意，不允许倾斜容器）

简单直接的思路是两层循环遍历每组可能的情况，时间复杂度O(n2)。可以进一步优化，采用两个指针l和r，初始化分别指向数组的两端，然后在向中间移动找到最大容量。如果l指向的数字小，则l需要右移才有可能获得更大容量，因为此时如果左移r，得到的容量肯定比左移r之前的容量小（高度已经被较小的l限制住了）。如果r指向的数字小，则需要左移r。这样，当l和r相遇的时候，最大的容量就是我们需要的。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution
{
public:
    int maxArea(vector<int> &height)
    {
        int l = 0, r = height.size() - 1, res = 0;
        while(l < r)
        {
            res = max(res, (r - l) * min(height[l], height[r]));
            if(height[l] < height[r])
                ++ l;
            else
                -- r;
        }
        return res;
    }
};