Description
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.
Discussion
这个问题的意思是在数轴上给出一些竖线。让我们找到两条线，使得它们和x轴构成的容器面积最大。
对于这个问题，我们可以给出两个指针lPos和rPos分别放在最左侧和最右侧。然后按照下面的方法进行：
如果height[lPos] < height[rPos]：lPos++； 否则： rPos–。
因为面积的大小是由高度比较低的竖线决定的。如果height[lPos] < height[rPos]，说明rPos所在的竖线比lPos所在的高，。如果把rPos向左移动，则面积必然减小，这些情况可以舍去。
算法的时间复杂度为O(n)。
C++ Code
class Solution {
public:
int maxArea(vector<int>& height) {
//初始两个指针指向左右两端
int lPos = 0;
int rPos = height.size() - 1;
int answer = 0;
//指针向中间靠拢
while(lPos < rPos)
{
answer = max(answer, (rPos - lPos) * min(height[lPos], height[rPos]));
//若左指针指向的竖线比较矮，则他向右移动一位，否则右边的左移一位。因为若是高的一端向低一端移动，容量不可能再增加，这种情况可以舍去
if(height[lPos] < height[rPos])
{
lPos++;
}
else
{
rPos--;
}
}
return answer;
}
};