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.

思路分析： 给定数组A[]，求直线((i, 0), (i, A[i]))、((j, 0), (j, A[j]))和X轴围成的体积重最多能装多少水。这个装水的多少是由abs(i - j)和min(A[i], A[j])共同决定的。两者的积越大，则能装的水越多。 所以我们先让abs(i - j)取最大值，通过左右两个指针，逐渐移动，逐步调整min(A[i], A[j])和abs(i - j)得到最大值。

C++参考代码：

class Solution
{
public:
    int maxArea(vector<int>& height)
    {
        int count = int(height.size());
        if (count == 0) return 0;
        int left = 0;
        int right = count - 1;
        int maxArea = 0;//最大面积
        int curArea = 0;//当前面积
        while (right > left)
        {
            curArea = min(height[left], height[right]) * (right - left);
            if (curArea > maxArea) maxArea = curArea;
            if (height[left] > height[right]) --right;
            else ++left;
        }
        return maxArea;
    }
};